Heap

Min-Max Heap
Min-Max Heap. Source: https://en.wikipedia.org/wiki/File:Min-max_heap.jpg

Heap is a balanced binary tree with a special property of each node. There are two types of Heap; Max-Heap and Min-Heap.

Max-Heap

Every node should be higher than its children. A node with the highest value should be root.

Min-Heap

Every node should be lower than its children. A node with the lowest value should be root.

Implementation

We want to able to get Left, Right, and Parent node on a heap. It can be represented much more efficiently by using an array. Let's say that the node is at the index. To get left, 2 x index + 1. To get right, 2 x index + 2. To get parent, (index - 1) / 2.

Heapify

Heapify is the process of inserting or removing an element into the heap. It places an element to the wrong position then find the right position for it. There are two types of Heapify; Sift Up and Sift Down.

Sift Up

An element is in the wrong position as a leaf, it has to be moved upwards towards the root to find its right position.

Sift Down

An element is in the wrong position as root, it has to be moved downwards towards the leaves to find its right position.

Insert

In array, an element would be added at the very end, and then Sift Up.

Remove

In array, after removing the value of the index, move over the last element to the removed one, and then Sift Down.

Access

It is easy to get as well as you know what the index is because it is an array and ordered.

Conclusion

The time complexity of Insert and Remove is Logarithmic, O (log n). But, for Access, it would be very fast, with time complexity is Constant, O(1).

Related Articles

Comments