Heap

Heap is a complete binary tree which has the property that every key of the root is the smaller or bigger than its all children and this sustains for all sub-tree in this tree. Usually there are only Max Heap or Min Heap.

Since it provides a time complexity of O(logn) with the Heapify operation, it can be used in sorting or quick trace the minimum or maximum element in an array because it provides O(1) time complexity to do so.

Implementation

Take Min Heap as an example. It has the operations of GetMin(), ExtractMin(), InsertKey(), Delete(), DecreaseKey(). The core operations in this data structure is Heapify, the python code of which is stated below:

def MinHeapify(i, harr):
    l, r, smallest = 2 * i + 1, 2 * i + 2, i
    if l < len(harr) and harr[l] < harr[i]:
        smallest = l
    if r < len(harr) and harr[r] < harr[smallest]:
        smallest = r
    if smallest != i:
        swap(i, smallest, harr)
        MinHeapify(smallest, harr)

For these operations, it all provides a time complexity of O(logn) to insert, extract min, delete and decrease key except get min for O(1). What needs to be mentioned is that insert and decrease key needs to traverse if the changed element is smaller than its parent. And extract min is realized through swapping the root element and the last element first then MinHeapifying the heap. The delete is implemented through decreasing the corresponding element by INT_MAX then extract the Min element from Heap.

Application

Heap is common used in sorting problems like sort a almost sorted array, get the kth element in an array and the typical heap sort.

Heap Sort

The thinking of heap sort is create a Max Heap first(O(n)). Then swap the root element with the last one, reduce the size of heap by 1 and MaxHeapify the new heap. Finally we repeat the last two steps until the size of the heap is 1. Thus, the time complexity of the Heap Sort is O(nlogn).