Heap
This article is copied from labualdong
Binary Heap is a perfect binary tree, and it is often saved in array. Its main applications are heap sort and priority queue.
The heap array looks as below,
Note: The heap will be saved from index 1, not from index 0, to avoid 0 as a divider of the calculation.
In a binary heap, we will manage its index as pointers for binary tree or linked list. Below are most used calculation of indexes of heap.
-
If we know a children’s index, its parent index = children’s index / 2
-
If we know a parent’s index, its left child index is root * 2
-
If we know a parent’s index, its right child index is root * 2 + 1
Max heap’s property is any node’s value is greater than its left and right children’s value.
Min heap’s property is any node’s value is less than its left and right children’s value.
Priority Queue Implementation:
Here we will build an example of Max Priority Queue, and we will use generic type Key to enable the priority queue to save any type of data.
First we will post all methods’ signature and implementation of helper methods.
public class MaxPQ
<Key extends Comparable<Key>> {
// 存储元素的数组
private Key[] pq;
// 当前 Priority Queue 中的元素个数
private int N = 0;
public MaxPQ(int cap) {
// 索引 0 不用，所以多分配一个空间
pq = (Key[]) new Comparable[cap + 1];
}
/* 返回当前队列中最大元素 */
public Key max() {
return pq[1];
}
/* 插入元素 e */
public void insert(Key e) {...}
/* 删除并返回当前队列中最大元素 */
public Key delMax() {...}
/* 上浮第 k 个元素，以维护最大堆性质 */
private void siftUp(int k) {...}
/* 下沉第 k 个元素，以维护最大堆性质 */
private void siftDown(int k) {...}
/* 交换数组的两个元素 */
private void swap(int i, int j) {
Key temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
/* pq[i] 是否比 pq[j] 小？ */
private boolean isLess(int i, int j) {
return pq[i].compareTo(pq[j]) < 0;
}
}
Second, we will implement heap’s 2 main functions siftUp() and siftDown().
-
siftUp(): If a node’s value is greater than its parent’s value, the node shall be swapped with its parent until its parent’s value greater than the node or the node reaches to the top.private void siftUp(int k) { // 如果浮到堆顶，就不能再上浮了 while (k > 1 && isless(2 * k, k)) { // 如果第 k 个元素比上层大 // 将 k 换上去 swap(2 * k, k); k = 2 * k; } } -
siftDown(): If a node’s value is less than any of its child, the node shall be swapped with the greater one of the two children until the both children less than the node or the node reaches to the leaf. Sift-down operation is bit more complex than sift-up. Sift-up only needs to compare a node with its parent. Sift-down operation needs to compare a node with both left and right children.private void siftDown(int k) { // 如果沉到堆底，就沉不下去了 while (k * 2 <= N) { // 先假设左边节点较大 int greaterChildIndex = k * 2; // 如果右边节点存在，比一下大小 if (k * 2 + 1 <= N && isLess(greaterChildIndex, (k * 2 + 1)) greaterChildIndex = k * 2 + 1; // 结点 k 比俩孩子都大，就不必下沉了 if (isLess(greaterChildIndex, k)) break; // 否则，不符合最大堆的结构，下沉 k 结点 swap(k, greaterChildIndex); k = greaterChildIndex; } }
Third, we will implement Priority Queue's `insert()` and `delMax()` functions.
`insert(Key e)`: We will add the elements at the last leaf and let it sift up to the proper position.
```java
public void insert(Key e) {
N++;
// 先把新元素加到最后
pq[N] = e;
// 然后让它上浮到正确的位置
siftUp(N);
}
delMax(): We will swap the top element with the leaf element, delete the swapped element, and sift up down the new top element to the proper position.
public Key delMax() {
// 最大堆的堆顶就是最大元素
Key max = pq[1];
// 把这个最大元素换到最后，删除之
swap(1, N);
pq[N] = null;
N--;
// 让 pq[1] 下沉到正确位置
siftDown(1);
return max;
}
Heapify
Heapify is the process of converting a binary tree array into a heap data structure. If we have an array, we can call Priority Queue’s insert function to build a heap. As well, we can also heapify an array into a heap. The difference of two ways are heapify is building a heap from bottom to top (build subtrees into a whole tree), and insert is building a heap from top to bottom (add each element at the top and sift down each element to the proper position). The different building directions influence the time complexity of two methods.
Nodes in a complete binary tree are located unevenly. Most of nodes are located at the bottom of a binary tree. If we build a tree from bottom as heapify, most of nodes from bottom, (n/2) takes time of O(1), (n/4) takes time of O(2)… When n approaches to infinity, time complexity approaches to O(n). If we build a tree from top to bottom as insert, most of nodes from bottom (n / 2) takes time of O(log n), (n/4) takes time O(log n/2)… When n approaches to infinity, time complexity approaches to O(nlogn).