堆(Heap)
完全二叉堆
完全二叉堆就是用完全二叉树实现的堆
鉴于完全二叉树的一些特性,二叉堆的底层(物理结构)一般用数组实现即可,
因为完全二叉树的结点都是相邻的
如果任意结点的值总是>=子结点的值,称为大根堆,最大堆,大顶堆,最大值都在根节点
如果任意结点的值总是<=子结点的值,称为小根堆,最小堆,小顶堆,最小值都在根节点

基本的接口设计

大根堆的实现
抽象类
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| @SuppressWarnings("unchecked") public abstract class AbstractHeap<E> implements Heap<E> { protected int size; protected Comparator<E> comparator;
public AbstractHeap(Comparator<E> comparator) { this.comparator = comparator; }
public AbstractHeap() { this(null); }
@Override public int size() { return size; }
@Override public boolean isEmpty() { return size == 0; }
protected int compare(E e1, E e2) { return comparator != null ? comparator.compare(e1, e2) : ((Comparable<E>)e1).compareTo(e2); } }
|
实现类
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220
|
@SuppressWarnings("unchecked") public class BinaryHeap<E> extends AbstractHeap<E> implements BinaryTreeInfo { private E[] elements; private static final int DEFAULT_CAPACITY = 10;
public BinaryHeap(E[] elements, Comparator<E> comparator) { super(comparator);
if (elements == null || elements.length == 0) { this.elements = (E[]) new Object[DEFAULT_CAPACITY]; } else { size = elements.length; int capacity = Math.max(elements.length, DEFAULT_CAPACITY); this.elements = (E[]) new Object[capacity]; for (int i = 0; i < elements.length; i++) { this.elements[i] = elements[i]; } heapify(); } }
public BinaryHeap(E[] elements) { this(elements, null); }
public BinaryHeap(Comparator<E> comparator) { this(null, comparator); }
public BinaryHeap() { this(null, null); }
@Override public void clear() { for (int i = 0; i < size; i++) { elements[i] = null; } size = 0; }
@Override public void add(E element) { elementNotNullCheck(element); ensureCapacity(size + 1); elements[size++] = element; siftUp(size - 1); }
@Override public E get() { emptyCheck(); return elements[0]; }
@Override public E remove() { emptyCheck();
int lastIndex = --size; E root = elements[0]; elements[0] = elements[lastIndex]; elements[lastIndex] = null;
siftDown(0); return root; }
@Override public E replace(E element) { elementNotNullCheck(element);
E root = null; if (size == 0) { elements[0] = element; size++; } else { root = elements[0]; elements[0] = element; siftDown(0); } return root; }
private void heapify() {
for (int i = (size >> 1) - 1; i >= 0; i--) { siftDown(i); } }
private void siftDown(int index) { E element = elements[index]; int half = size >> 1; while (index < half) {
int childIndex = (index << 1) + 1; E child = elements[childIndex];
int rightIndex = childIndex + 1;
if (rightIndex < size && compare(elements[rightIndex], child) > 0) { child = elements[childIndex = rightIndex]; }
if (compare(element, child) >= 0) break;
elements[index] = child; index = childIndex; } elements[index] = element; }
private void siftUp(int index) {
E element = elements[index]; while (index > 0) { int parentIndex = (index - 1) >> 1; E parent = elements[parentIndex]; if (compare(element, parent) <= 0) break;
elements[index] = parent;
index = parentIndex; } elements[index] = element; }
private void ensureCapacity(int capacity) { int oldCapacity = elements.length; if (oldCapacity >= capacity) return;
int newCapacity = oldCapacity + (oldCapacity >> 1); E[] newElements = (E[]) new Object[newCapacity]; for (int i = 0; i < size; i++) { newElements[i] = elements[i]; } elements = newElements; }
private void emptyCheck() { if (size == 0) { throw new IndexOutOfBoundsException("Heap is empty"); } }
private void elementNotNullCheck(E element) { if (element == null) { throw new IllegalArgumentException("element must not be null"); } }
@Override public Object root() { return 0; }
@Override public Object left(Object node) { int index = ((int)node << 1) + 1; return index >= size ? null : index; }
@Override public Object right(Object node) { int index = ((int)node << 1) + 2; return index >= size ? null : index; }
@Override public Object string(Object node) { return elements[(int)node]; } }
|
快速建堆
自上而下的上滤
等价于挨个元素进行添加
| for (int i = 1; i < elements.length; i++) { siftUp(i); }
|
自下而上的下滤
类似于删除,从下而上慢慢的建成堆
| for (int i = (size >> 1) - 1; i >= 0; i--) { siftDown(i); }
|
性能对比

自上而下的下滤的建堆,比较多的结点在做工作量少的事情,自上而下的上滤正好相反
堆的应用场景
优先级队列

Java里的优先队列是PriorityQueue
可以用来解决Top k问题
在无序数组中找到第k个,最大/最小的元素