Before diving into heap data structure, let's first understand what is a complete binary tree.

Complete binary tree

A complete binary tree is a tree in which all levels are completely filled, except possibly the lowest one which is filled from left. The below diagram can help visualize a complete binary tree.

Heap

A heap is a special complete binary tree which is of two types:-

Max-Heap: Every node in the tree should have a value that is greater than or equal to the values of all its child nodes. This rule applies to the root node as well as every other node within the tree. So, the root node will be the greatest element.

Min-Heap: Every node in the tree should have a value that is less than or equal to the values of all its child nodes. This rule applies to the root node as well as every other node within the tree. So, the root node will be the smallest element.

Note:- The above is not the only possible way to form a heap, for example, if you exchange the position of 56 and 72, it would still be a valid min heap.

How to store a heap?

Heaps can be stored using a class with data, left and right nodes.

class Node {
       int data;
       Node* left;
       Node* right;
}

But, using the property of complete binary tree(remember? complete binary trees are filled), we can simplify this and represent heap in the form of an array.

For now, we are going to focus only on min-heap, max-heap is just the reverse, so if you min heap you already know max-heap

Operations associated with min heap:-

1. Inserting an element.

2. Removing the min element.

1. Inserting an element.

We insert an element at the bottommost available position from the left of the tree or the last index in terms of the array. But, this may not be the correct position for that element, so we have to bubble it up to the right position. We compare its value with the parent node and if it's greater we exchange the position. The following picture depicts how a node is inserted into the tree.

• Inserting node 8 at the bottommost available position. But this is not the correct position, so we need to bubble it up, starting with swapping with 25.

• Still the element 8 is not at the correct position, we will bubble it up further more by exchanging it with node 10.

• Now node 8 has reached the correct position, so we stop the bubbling up process.

2. Removing minimum element from the min heap.

The minimum element is always at the topmost position (or the first element of the array). When we remove it, it creates an empty spot. This empty spot is filled by bottom rightmost node (the last element of the array). This element then needs to be bubble down to the right position.

• Node 6 is the minimum element which needs to be removed.

• 

• We remove the node 6 but that place becomes empty, we now swap it with the last node (72 here).

  

• We moved 72 to the topmost position, but it is not the correct position for it, so we need to bubble it down. We will swap it with the left or right node whichever is minimum. Here, we swap it with node 10.

• 

  We repeat the above operation, Now will compare 72 with 22 and 25, and since 22 (the left node) being minimum, we swap node 72 with it.

• 

  We keep on doing it unless we get the right position for node 72.

  

  

Complexities

Heaps can retrieve, insert, and delete elements in O(log n)

Conclusion

In this, I have covered the theoretical part of the heap data structures. Please read my second part on how to implement it here :- https://jainshreyansh.com/heap-data-structures-part-1

Follow and upvote my post, if you find this useful :)