Heap

Binary Tree Structure:

• The heap is a complete binary tree, meaning that all levels of the tree are completely filled, except possibly for the last level, which is filled from left to right.
• This structure allows for efficient storage of elements in an array, where the array indices correspond to the positions of nodes in the tree.

Array Representation:

• The elements of the heap are stored in an array, and the relationship between parent and child nodes is maintained through the array indices.
• For any node at index i:
• Its left child is at index 2i + 1.
• Its right child is at index 2i + 2.
• Its parent is at index floor((i-1)/2).

There are two main types of heaps:

Get Hsuzarni maung’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Max Heap Tree: In a max heap, the key of the parent node is always greater than or equal to the keys of its children. The maximum element is at the root.

Fig. Max Heap Tree

Array representation of Max Heap Tree

Min Heap Tree: In a min heap, the key of the parent node is always less than or equal to the keys of its children. The minimum element is at the root.

Fig. Min Heap Tree

Array representation of Min Heap Tree

Binary Heap Insertion:

In a binary heap, the usual operation for insertion involves adding the new element to the next available position in the heap and then “bubbling up” or “sifting up” the element to its correct position to maintain the heap property.

Time Complexity:

The time complexity for binary heap insertion is O(log n), where n is the number of elements in the heap. This is because the height of a binary heap is log(n), and during the insertion process, you might need to traverse the height of the tree (in the worst case) to restore the heap property.

Example:

Let’s consider a max heap:

1. Add the new element at the bottom.
2. Compare the new element with its parent.
3. If the new element is greater than its parent, swap them.
4. Repeat steps 2–3 until the heap property is restored.

Now, let’s insert a new element, say 9, into the heap:

Binary Heap Insertion

Max Heap Deletion:

1. Remove the Root: Remove the maximum element (which is at the root of the max heap). In a max heap, this is the topmost element.
2. Replace with Last Element: Replace the removed element with the last element (bottom-rightmost element) in the heap. This maintains the complete binary tree property.
3. Heapify Down (Bubbling Down): Compare the new root with its children. Swap it with the larger of its children until the max heap property is restored.

Now, let’s delete the root (10):

Max Heap Deletion