Introduction to Heaps

Heap is a very useful data structure that every programmer should know well. The heap data structure is used in Heap Sort, Priority Queues. The understanding of heaps helps us to know about memory management. In this blog, we will discuss the structure, properties, and array implementation of heaps.

Heap Structure

Heap is a complete binary tree with some property. There are two types of a heap on the basis of the property.

  • Max-Heap: The key present at any node must be greater than the keys present at both of its children. The largest key is at the root node.
  • Min-Heap: The key present at any node must be smaller than the keys present at both of its children. The smallest key is at the root node.
Compelete Tree - A tree in which all levels are completely filled except possibly the last level and last level has all keys left as possible.

Array Representation

A binary heap is represented as an array. The representation follows some property.

  • The root of the tree will be at Arr[0].
  • For any node at Arr[i], its left and right children will be at Arr[2*i + 1] and Arr[2*i+2] respectively.
  • For any node at Arr[i], its parent node will be at Arr[(i-1)/2].

Why Array?

Since a Binary Heap is a Complete Binary Tree, it can be easily represented as an array and array-based representation is space-efficient.

Level Order Traversal of the heap will give the order in which elements are filled in the array.

Applications of Heap

  1. Heap Sort : Heap Sort uses Binary Heap to sort an array in O(nlogn).
  2. Priority Queue: It uses binary heap to efficient implement operations insert(), delete(), extract_max(), update() in O(logn) time.
  3. Graph Algorithms: Some of the Graph Algorithms also use heaps to reduce its time complexity like Dijkstra’s Algorithm and Minimum Spanning Tree.
  4. K-way merge: A heap data structure is useful to merge many already-sorted input streams into a single sorted output stream.
  5. Order statistics : The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array.

Suggested Problems to solve

Happy coding! Enjoy Algorithms.