An Intro to Heap Data Structure
Tags: algorithms, beginners, datastructure
Published: 2022-06-03 14:12:11

### 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**


![Array Representation](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/bed5h66a7glqt7bzttpz.png)
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**:


![Full binary tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vwb8wc3ods32ji03sxdd.jpg)

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**:

![Complete binary tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pmjsqfkr8fj5ukkksmy7.jpg)

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**


![Array representation of not complete tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lwg90iuvk8va42hdg25m.png)

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

---

**Heap**
- Heap is a complete binary tree.

![Min heap vs max heap](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7n74ytf4ygcjip7apqzh.png)

**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.


![Heapify](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b3wvao1rwynj8pyb8h3h.png)

- 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.
2. 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.