Heap

Posted on | In

Heap is a tree-based data structure which satisfies the heap ordering property:

  • If it is a max-heap, the value of any node is greater than or equal to the value of its children, with the maximum value at the root
  • If it is a min-heap, the value of any node is less than or equal to the value of its children, with the minimum value at the root

The binary heap is the most common implementation of a heap. It is a complete binary tree where every level (except possibly the last one) is completely filled, and all nodes are as far let as possible. Thus, a binary heap can be implemented based on an array instead of a binary tree. Suppose the index of a node is i, then

1
2
3
int leftChild = i * 2 + 1;  // index of its left child
int rightChild = i * 2 + 2; // index of its right child
int parent = (i - 1) / 2;   // index of its parent

When an element is inserted or removed, the heap needs to be adjusted to maintain the ordering property, and the time complexity depends on the height of the heap, i.e. O(log(n)). Unlike a sorted array which takes O(n*log(n)) to sort and O(1) to fetch the next element, it takes O(n*log(n)) to build a heap and O(log(n)) to adjust the heap for fetching the next element, so it does not make sense to use heap to sort a fixed size collection (aka. heapsort), but if we need to sort out the top k elements from a stream or a file which cannot be fit into memory, a heap is exactly what we need.

Implementation of heap

There are two operations on a heap:

  • Insertion: insert the new element at the rear of the array and then adjust the heap using bottom-up approach
  • Removal: remove the top element and then adjust the heap using top-down approach

Insert a new element

1
2
3
4
5
6
7
8
9
10
11
public void insert(int[] maxHeap, int len, int num) {
    maxHeap[len++] = num;
    // bottom-up adjust
    int i = len - 1;
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (maxHeap[parent] >= maxHeap[i]) break;
        swap(maxHeap, parent, i);
        i = parent;
    }
}

Remove the top element

Implementation 1: replace the element at the top with the one at the rear and then adjust the heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void remove(int[] maxHeap, int len) {
    maxHeap[0] = maxHeap[--len];
    // top-down adjust
    int i = 0;
    while (i < len) {
        int left = i * 2 + 1;
        int right = left + 1;
        if (left >= len) break;
        int j = left;
        if (right < len && maxHeap[right] > maxHeap[left]) {
            j = right;
        }
        if (maxHeap[i] >= maxHeap[j]) break;
        swap(maxHeap, i, j);
        i = j;
    }
}

Implementation 2: remove the element at the top and then replace the blank with its child

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void remove(int[] maxHeap, int len) {
    int i = 0;
    while (i < len) {
        int left = i * 2 + 1;
        int right = left + 1;
        if (left >= len) break;
        int j = left;
        if (right < len && maxHeap[right] > maxHeap[left]) {
            j = right;
        }
        maxHeap[i] = maxHeap[j];
        i = j;
    }

    if (i < len) {
        maxHeap[i] = maxHeap[--len];
    }
}