Heap in Data Structures

Amit Kumar Ghosh 19 min read

08 Jun 2023

Intermediate

335 Views

Heap

Introduction

Data structures allow us to store and access large amounts of information in an efficient manner. One such data structure is the heap, a specialized tree-based collection that can effectively store and retrieve data. Heaps can be used for many purposes including sorting, searching, maintaining databases, manipulating networks, and much more. Our article will explore what a heap is in detail as well as provide examples of its use cases. Reading this article will help you better understand the principles of heaps along with discovering how it has become increasingly important for managing big data.

What is heap in data structure

A heap is a fundamental data structure in computer science that is used to store and manage a collection of items in a specific way. The heap is essentially a tree-like structure where each node has a key value and one or more child nodes, and the key of each parent node is less than or equal to the keys of its child nodes. This ordering property is called the heap property, and it is what makes heaps such powerful tools for solving a variety of data processing problems. By using heaps, programmers can efficiently find, insert, or delete items from a collection with a minimum number of operations, making heaps an essential component of many software applications. Whether the user is building a search engine, writing a game, or working on a financial system, understanding the heap data structure is a must for any programmer.

Types of Heap Data Structure

There are two main types of heap data structures:

Max Heap in data structure: A binary tree where the value of each node is greater than or equal to the values of its children nodes. This means that the maximum element is always at the root node.

Here is an algorithm for constructing a Max Heap from an array of values:

Start by initializing an empty heap.
Iterate through the array of values, inserting each value into the heap.
To insert a value into the heap:

Add the value to the end of the heap.
Compare the value to its parent node. If the value is greater than the parent node, swap the value with its parent node.
Continue swapping the value with its parent node until the value is in the correct position in the heap (i.e., the value is greater than or equal to its parent node).

Once all values have been inserted into the heap, the Max Heap construction is complete.

 public class MaxHeap {
     private int[] heap;
     private int size;
     private int capacity;
     public MaxHeap(int capacity) {
         this.capacity = capacity;
         this.size = 0;
         this.heap = new int[capacity];
     }
     private int parent(int i) {
         return (i - 1) / 2;
     }
     private int leftChild(int i) {
         return 2 * i + 1;
     }
     private int rightChild(int i) {
         return 2 * i + 2;
     }
     private void swap(int i, int j) {
         int temp = heap[i];
         heap[i] = heap[j];
         heap[j] = temp;
     }
     private void siftUp(int i) {
         while (i > 0 && heap[parent(i)] < heap[i]) {
             swap(i, parent(i));
             i = parent(i);
         }
     }
     private void siftDown(int i) {
         int maxIndex = i;
         int l = leftChild(i);
         if (l <= size && heap[l] > heap[maxIndex]) {
             maxIndex = l;
         }
         int r = rightChild(i);
         if (r <= size && heap[r] > heap[maxIndex]) {
             maxIndex = r;
         }
         if (i != maxIndex) {
             swap(i, maxIndex);
             siftDown(maxIndex);
         }
     }
     public void insert(int p) {
         if (size == capacity) {
             throw new IndexOutOfBoundsException("Heap is full");
         }
         heap[size] = p;
         size++;
         siftUp(size - 1);
     }
     public int extractMax() {
         int result = heap[0];
         heap[0] = heap[size - 1];
         size--;
         siftDown(0);
         return result;
     }
     public boolean isEmpty() {
         return size == 0;
     }
     public int size() {
         return size;
     }
     public void printHeap() {
         for (int i = 0; i < size; i++) {
             System.out.print(heap[i] + " ");
         }
         System.out.println();
     }
 }

Min Heap in data structure: A binary tree where the value of each node is less than or equal to the values of its children nodes. This means that the minimum element is always at the root node.

Here is an algorithm to construct a min heap from an input array:

Start with an empty heap array and iterate through the input array, adding each element to the heap array.
Starting with the last parent node in the heap array (i.e., the node at index (n-2)/2, where n is the number of elements in the heap array), perform the following steps for each parent node in reverse order:

Compare the parent node with its children. If the parent node is greater than its child, swap the parent with the smallest child.
Continue this process recursively down the heap until the parent node is smaller than its children or has no children left.
After all parent nodes have been processed, the heap array is a valid min heap.

public class MinHeap {
     private int[] heap;
     private int size;
     private int maxSize;
     private static final int FRONT = 1;
     public MinHeap(int maxSize) {
         this.maxSize = maxSize;
         this.size = 0;
         heap = new int[this.maxSize + 1];
         heap[0] = Integer.MIN_VALUE;
     }
     private int parent(int pos) {
         return pos / 2;
     }
     private int leftChild(int pos) {
         return (2 * pos);
     }
     private int rightChild(int pos) {
         return (2 * pos) + 1;
     }
     private boolean isLeaf(int pos) {
         return pos > (size / 2) && pos <= size;
     }
     private void swap(int fpos, int spos) {
         int tmp;
         tmp = heap[fpos];
         heap[fpos] = heap[spos];
         heap[spos] = tmp;
     }
     private void minHeapify(int pos) {
         if (!isLeaf(pos)) {
             if (heap[pos] > heap[leftChild(pos)] || heap[pos] > heap[rightChild(pos)]) {
                 if (heap[leftChild(pos)] < heap[rightChild(pos)]) {
                     swap(pos, leftChild(pos));
                     minHeapify(leftChild(pos));
                 } else {
                     swap(pos, rightChild(pos));
                     minHeapify(rightChild(pos));
                 }
             }
         }
     }
     public void insert(int element) {
         if (size >= maxSize) {
             return;
         }
         heap[++size] = element;
         int current = size;
         while (heap[current] < heap[parent(current)]) {
             swap(current, parent(current));
             current = parent(current);
         }
     }
     public void print() {
         for (int i = 1; i <= size / 2; i++) {
             System.out.print("Parent: " + heap[i] + " Left Child: " + heap[2 * i]
                   + " Right Child: " + heap[2 * i + 1]);
             System.out.println();
         }
     }
     public int remove() {
         int popped = heap[FRONT];
         heap[FRONT] = heap[size--];
         minHeapify(FRONT);
         return popped;
     }
 }

Both min heap and max heap can be implemented using arrays or linked lists. In addition to these two basic types of heaps, there are also other variants such as Fibonacci heap, Binomial heap, Pairing heap, etc., which are more complex but can offer better time complexity for specific use cases.

Heap Operations in Data Structure

Insertion

To insert a new element into a heap, it is added as a new leaf node and then "bubbled up" to its correct position to maintain the heap property. For a min-heap, the new element is compared with its parent node and swapped if it is smaller. The swapping is repeated until the new element is in its correct position. For a max-heap, the same process is followed, but the new element is compared with its parent node and swapped if it is larger.

Deletion

To remove an element from a heap, the root node (which is always the minimum or maximum value) is removed and replaced with the last leaf node. The new root is then "bubbled down" to its correct position to maintain the heap property. For a min-heap, the new root is compared with its children and swapped with the smallest child if it is larger. The swapping is repeated until the new root is in its correct position. For a max-heap, the same process is followed, but the new root is compared with its children and swapped with the largest child if it is smaller.

Peek

To get the minimum or maximum value in a heap without removing it, the value of the root node is returned.

Heapify

To convert an array of values into a heap, the array is first initialized as a complete binary tree. Then, each node is "bubbled down" to its correct position to maintain the heap property. This is done in a bottom-up manner, starting from the last non-leaf node and working toward the root.

Heap sort

Heap sort is a sorting algorithm that uses a heap data structure to sort an array of values. First, the array is converted into a heap using the heapify operation. Then, the minimum or maximum value is repeatedly removed from the heap and added to a sorted list until all values have been removed. The resulting list is the sorted array

def swap(a, b):
     temp = b
     b = a
     a = temp
 def heapify(hT, i):
     size = len(hT)
     largest = i
     l = 2 * i + 1
     r = 2 * i + 2
     if l < size and hT[l] > hT[largest]:
         largest = l
     if r < size and hT[r] > hT[largest]:
         largest = r
     if largest != i:
         swap(hT[i], hT[largest])
         heapify(hT, largest)
 def insert(hT, newNum):
     size = len(hT)
     if size == 0:
         hT.append(newNum)
     else:
         hT.append(newNum)
         for i in range(size//2-1, -1, -1):
             heapify(hT, i)
 def deleteNode(hT, num):
     size = len(hT)
     i = 0
     for i in range(size):
         if num == hT[i]:
             break
     swap(hT[i], hT[size-1])
     hT.pop()
     for i in range(size//2-1, -1, -1):
         heapify(hT, i)
 def printArray(hT):
     for i in range(len(hT)):
         print(hT[i], end=" ")
     print()
 # Testing the functions
 heapTree = []
 insert(heapTree, 3)
 insert(heapTree, 4)
 insert(heapTree, 9)
 insert(heapTree, 5)
 insert(heapTree, 2)
 print("Max-Heap array: ", end="")
 printArray(heapTree)
 deleteNode(heapTree, 4)
 print("After deleting an element: ", end="")
 printArray(heapTree)


 import java.util.ArrayList;
 class MaxHeap {
     private static void swap(int[] arr, int i, int j) {
         int temp = arr[j];
         arr[j] = arr[i];
         arr[i] = temp;
     }
     private static void heapify(ArrayList<Integer> heapTree, int i) {
         int size = heapTree.size();
         int largest = i;
         int left = 2 * i + 1;
         int right = 2 * i + 2;
         if (left < size && heapTree.get(left) > heapTree.get(largest)) {
             largest = left;
         }
         if (right < size && heapTree.get(right) > heapTree.get(largest)) {
             largest = right;
         }
         if (largest != i) {
             swap(heapTree, i, largest);
             heapify(heapTree, largest);
         }
     }
     private static void insert(ArrayList<Integer> heapTree, int newNum) {
         int size = heapTree.size();
         if (size == 0) {
             heapTree.add(newNum);
         } else {
             heapTree.add(newNum);
             for (int i = size / 2 - 1; i >= 0; i--) {
                 heapify(heapTree, i);
             }
         }
     }
     private static void deleteNode(ArrayList<Integer> heapTree, int num) {
         int size = heapTree.size();
         int i;
         for (i = 0; i < size; i++) {
             if (num == heapTree.get(i)) {
                 break;
             }
         }
         swap(heapTree, i, size - 1);
         heapTree.remove(size - 1);
         for (int j = size / 2 - 1; j >= 0; j--) {
             heapify(heapTree, j);
         }
     }
     private static void printArray(ArrayList<Integer> arr) {
         for (int i : arr) {
             System.out.print(i + " ");
         }
         System.out.println();
     }
     public static void main(String[] args) {
         ArrayList<Integer> heapTree = new ArrayList<>();
         insert(heapTree, 3);
         insert(heapTree, 4);
         insert(heapTree, 9);
         insert(heapTree, 5);
         insert(heapTree, 2);
         System.out.print("Max-Heap array: ");
         printArray(heapTree);
         deleteNode(heapTree, 4);
         System.out.print("After deleting an element: ");
         printArray(heapTree);
     }
 }


 
 // Max-Heap data structure in C++
 #include <iostream>
 #include <vector>
 using namespace std;
 void swap(int *a, int *b)
 {
   int temp = *b;
   *b = *a;
   *a = temp;
 }
 void heapify(vector<int> &hT, int i)
 {
   int size = hT.size();
   int largest = i;
   int l = 2 * i + 1;
   int r = 2 * i + 2;
   if (l < size && hT[l] > hT[largest])
     largest = l;
   if (r < size && hT[r] > hT[largest])
     largest = r;
   if (largest != i)
   {
     swap(&hT[i], &hT[largest]);
     heapify(hT, largest);
   }
 }
 void insert(vector<int> &hT, int newNum)
 {
   int size = hT.size();
   if (size == 0)
   {
     hT.push_back(newNum);
   }
   else
   {
     hT.push_back(newNum);
     for (int i = size / 2 - 1; i >= 0; i--)
     {
       heapify(hT, i);
     }
   }
 }
 void deleteNode(vector<int> &hT, int num)
 {
   int size = hT.size();
   int i;
   for (i = 0; i < size; i++)
   {
     if (num == hT[i])
       break;
   }
   swap(&hT[i], &hT[size - 1]);
   hT.pop_back();
   for (int i = size / 2 - 1; i >= 0; i--)
   {
     heapify(hT, i);
   }
 }
 void printArray(vector<int> &hT)
 {
   for (int i = 0; i < hT.size(); ++i)
     cout << hT[i] << " ";
   cout << "\n";
 }
 int main()
 {
   vector<int> heapTree;
   insert(heapTree, 3);
   insert(heapTree, 4);
   insert(heapTree, 9);
   insert(heapTree, 5);
   insert(heapTree, 2);
   cout << "Max-Heap array: ";
   printArray(heapTree);
   deleteNode(heapTree, 4);
   cout << "After deleting an element: ";
   printArray(heapTree);
 }

Output

Max-Heap array: 9 5 4 3 2 
After deleting an element: 9 5 2 3

Applications of heap

Applications of the Heap are:

Priority Queues: One of the most common uses of heap data structure is to implement priority queues. A priority queue is a collection of elements where each element has a priority associated with it. Elements with higher priority are dequeued before elements with lower priority. The heap data structure is well suited for this application because it allows for efficient insertion and removal of elements while maintaining the priority order.
Graph Algorithms: Heap data structure can be used to efficiently implement a number of graph algorithms, including Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm. In these algorithms, the heap data structure is used to store the vertices or edges of the graph in a priority queue, with the priority being the distance or weight of the path.
Sorting: Heap sort is a sorting algorithm that uses the heap data structure to sort an array of elements. The basic idea of the algorithm is to first build a heap from the input array and then repeatedly remove the largest element from the heap and place it at the end of the sorted array.
Memory Management: The heap data structure is also used for memory management in programming languages like C and C++. In these languages, the heap is a region of memory where dynamically allocated memory is stored. The heap data structure is used to keep track of the free and allocated memory blocks in the heap.
Event-driven Simulation: The heap data structure is used in event-driven simulation, where events are stored in a priority queue based on their time of occurrence. The heap data structure allows for the efficient insertion and removal of events while maintaining the correct ordering.

Summary

To conclude, a heap in the data structure is certainly a powerful and useful tool for any programmer. In this article, we have explored the wide range of capabilities these structures can enable for applications, from sorting and organizing to preventing memory overflow errors. Learning about heaps has revealed that they are highly beneficial and can provide some unique advantages over other solutions. This article has highlighted the importance of having a detailed understanding of data structures when building programs or analyzing code. With this knowledge in mind, we encourage developers to explore the full potential of heaps. We also urge them to consider implementing heaps into projects so that they can gain an extra advantage from working with such fantastic data structure technology. Check out tutorials and more information on heap data structure today!