An Intro to Heap Data Structure

Topics that is going to be discussed-

1. Array Representation of BT
2. Complete Binary Tree
3. Heap
4. Insert & Delete
5. Heap Sort
6. Heapify
7. Priority Queue

---

Array Representation of Binary Tree

If a Node is at index -> i

• It's left child is at -> 2*i
• It's right child is at -> 2*i+1
• It's parent is at -> i/2

If there are missing nodes in the Binary Tree, you need leave the corresponding index of the array blank.

---

Full Binary Tree V Complete Binary Tree:

So, the number of nodes of full binary tree is - (2^h+1)-1
Here, h is the height of the binary tree

Complete Binary Tree:

In a complete binary tree, if we traverse the binary tree in a level order fashion then we cannot have a missing node in between two nodes. So, a complete binary tree can be a full binary tree up until the binary tree's h-1.

Example of a not Complete binary tree in array representation

Height of a Complete Binary Tree will always be log(n)

---

Heap

• Heap is a complete binary tree.

Min heap - Min heap is a complete binary tree satisfying the condition that each node is having the element smaller or equal to all its descendants.

Max heap - Min heap is a complete binary tree satisfying the condition that each node is having the element greater or equal to all its descendants.

Time taken for a insertion in a Heap-

• minimum: O(1)

• maximum: O(logn)

• If you delete from a max-heap you will get the next largest element.

• If you delete from a min-heap you will get the next smallest element.

---

Heap Sort:

• Step-1: For a given set of elements create a heap.
• Step-2: Delete all the elements one by one.

Hence, all the elements will be sorted.

Time Complexity for Heap Sort: O(nlogn)

---

Heapify:

1. While creating the heap in step-1 instead of going through the array from left to right, we go through it by going from right to left. You might wonder how this helps. If you recall heap element deletion procedure you will recall that the element that is to be deleted is sent to the bottom. We use that principle to build the heap in the heapify procedure. If a element does not have a children we just create the heap but if an element does posses children than we compare the children with parent and adjust the elements accordingly.

• Time complexity for Heapify is O(n) which is better than the O(nlogn) time complexity we get by following the create heap procedure.

---

Priority Queue: In a priority queue elements should be deleted in the order of higher priority.

1.There can be two kinds priority - smaller number -> higher priority or larger number -> higher priority.

1. For smaller number -> higher priority you can use min-heap and for larger number -> higher priority you can use max-heap.

Since, insertion and deletion in a heap takes O(logn) time it is a great data structure for implementing priority queues.