Applications of Heap Data Structure

Last Updated : 01 Jun, 2023

Introduction:

Priority Queues: Heaps are commonly used to implement priority queues, where elements with higher priority are extracted first. This is useful in many applications such as scheduling tasks, handling interruptions, and processing events.
Sorting Algorithms: Heapsort, a comparison-based sorting algorithm, is implemented using the Heap data structure. It has a time complexity of O(n log n), making it efficient for large datasets.
Graph algorithms: Heaps are used in graph algorithms such as Dijkstra’s shortest path algorithm, Prim’s minimum spanning tree algorithm, and the A* search algorithm.
File Compression: Heaps are used in data compression algorithms such as Huffman coding, which uses a priority queue implemented as a min-heap to build a Huffman tree.
Dynamic programming: Heaps are used in dynamic programming algorithms such as the greedy algorithm, where elements are processed in order of priority.
Medical Applications: In medical applications, heaps are used to store and manage patient information based on priority, such as vital signs, treatments, and test results.
External sorting: Heaps are used in external sorting algorithms to sort large datasets that do not fit into memory, by processing chunks of data in a priority queue.
Load balancing: Heaps are used in load balancing algorithms to distribute tasks or requests to servers, by processing elements with the lowest load first.
Online algorithms: Heaps are used in online algorithms, where elements are processed in real-time as they arrive, such as recommendation systems, event processing, and streaming data.
Stock market: Heaps are used in financial applications, such as stock market analysis and algorithmic trading, to process and manage large amounts of stock data based on priority.

Heap Data Structure is generally taught with Heapsort. Heapsort algorithm has limited uses because Quicksort is better in practice. Nevertheless, the Heap data structure itself is enormously used.

Following are some uses other than Heapsort.

Priority Queues: Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also in O(logn) time which is a O(n) operation in Binary Heap. Heap Implemented priority queues are used in Graph algorithms like Prim’s Algorithm and Dijkstra’s algorithm.

Order statistics: The Heap data structure can be used to efficiently find the kth smallest (or largest) element in an array. See method 4 and 6 of this post for details.

References:

http://net.pku.edu.cn/~course/cs101/2007/resource/Intro2Algorithm/book6/chap07.htm http://en.wikipedia.org/wiki/Heap_%28data_structure%29

Heap data structures have a number of applications due to their ability to provide fast access to the smallest or largest element in a collection. Some common applications of heap data structures include:

Priority queues: Heaps can be used to implement priority queues, where each element has a priority associated with it and elements with higher priorities are given priority over elements with lower priorities.

Sorting: Heapsort is a comparison-based sorting algorithm that uses a heap data structure to sort a list of elements. It has a time complexity of O(n*log(n)).

Graph algorithms: Heaps are often used in graph algorithms, such as Dijkstra’s shortest path algorithm and the A* search algorithm, to efficiently determine the next element to be processed.

Median maintenance: Heaps can be used to maintain the median of a stream of numbers by using a max-heap to store the smaller half of the numbers and a min-heap to store the larger half.

Resource allocation: Heaps can be used to efficiently allocate resources in a system, such as memory blocks or CPU time, by assigning a priority to each resource and processing requests in order of priority.

Selection algorithms: Heaps can be used in selection algorithms, such as the quickselect algorithm, to efficiently find the kth smallest element in a list.

Advantages Of Applications of Heap Data Structure

Efficient: Heaps have an average time complexity of O(log n) for inserting and deleting elements, making them efficient for large datasets.
Flexible: Heaps can be implemented as either a max-heap or a min-heap, making them flexible to use for different types of applications, such as priority queues or sorting algorithms.
Dynamic: Heaps can be dynamically resized as elements are inserted or deleted, making them suitable for dynamic applications that require adding or removing elements in real-time.
Simple: Heaps have a simple structure, with a complete binary tree, making them easy to implement and understand.
Stable: Heaps are a stable data structure, meaning that elements are processed in order of priority, making them suitable for applications where order matters.
Priority-based: Heaps allow elements to be processed based on priority, making them suitable for real-time applications, such as load balancing, medical applications, and stock market analysis.
Scalable: Heaps can scale to handle large amounts of data, making them suitable for big data applications, such as external sorting and file compression.
Memory-efficient: Heaps are memory-efficient, as they only store the elements that are necessary for processing, making them suitable for embedded systems and devices with limited memory.
In-place: Heaps can be implemented in-place, without the need for additional memory, making them efficient for memory-constrained applications.
Parallelizable: Heaps can be parallelized, allowing multiple processors to work on the same data structure, making them suitable for multi-core systems and high-performance computing.

C++

//implementation of heap data structure in C++ by Jatin sharma
#include <iostream>
#include <vector>
using namespace std;
void swapping(int *x, int *y) // swap-function - to swapping two number
{
int t = *y;
*y = *x;
*x = t;
}
void insertHeapTree(vector<int> &hT, int val)
{
int treeSize = hT.size();
if (treeSize == 0)
{
hT.push_back(val);
}
else
{
hT.push_back(val);
}
}
void deleteValue(vector<int> &hT, int val)
{
int treeSize = hT.size();
int i;
for (i = 0; i < treeSize; i++)
{
if (val == hT[i])
break;
}
swapping(&hT[i], &hT[treeSize - 1]);
hT.pop_back();
}
void printArray(vector<int> &hT)
{
for (int i = 0; i < hT.size(); ++i)
cout << hT[i] << " ";
cout << "\n";
}
int main()
{
vector<int> heapTree;
int delValue;
insertHeapTree(heapTree, 3);
insertHeapTree(heapTree, 4);
insertHeapTree(heapTree, 9);
insertHeapTree(heapTree, 5);
insertHeapTree(heapTree, 12);
insertHeapTree(heapTree, 7);
insertHeapTree(heapTree, 15);
insertHeapTree(heapTree, 20);
cout << "HEAP DATA STRUCTURE - INSERT & DELETE OPERATION\n";
cout << "Inserted Values in Heap-Tree\n";
printArray(heapTree);
cout << "Enter one value from above heap-tree values -  to delete in Heap-Tree:  \n";
cin>>delValue;
deleteValue(heapTree, delValue);
cout << "\nAfter deleting an element: ";
printArray(heapTree);
}

Java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Main {
 
    // function to swap two numbers
    public static void swapping(List<Integer> arr, int x,
                                int y)
    {
        int t = arr.get(y);
        arr.set(y, arr.get(x));
        arr.set(x, t);
    }
 
    // function to insert a value into the heap tree
    public static void insertHeapTree(List<Integer> hT,
                                      int val)
    {
        int treeSize = hT.size();
        if (treeSize == 0) {
            hT.add(val);
        }
        else {
            hT.add(val);
            int i = treeSize;
            while (i != 0
                   && hT.get(i) > hT.get((i - 1) / 2)) {
                swapping(hT, i, (i - 1) / 2);
                i = (i - 1) / 2;
            }
        }
    }
 
    // function to delete a value from the heap tree
    public static void deleteValue(List<Integer> hT,
                                   int val)
    {
        if (hT.size() == 0) {
            return;
        }
 
        int treeSize = hT.size();
        int i = 0;
        for (i = 0; i < treeSize; i++) {
            if (val == hT.get(i)) {
                break;
            }
        }
 
        if (i != hT.size()) {
            swapping(hT, i, treeSize - 1);
        }
        hT.remove(hT.size() - 1);
    }
 
    // function to print the heap tree
    public static void printArray(List<Integer> hT)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < hT.size(); i++) {
            sb.append(hT.get(i)).append(" ");
        }
        System.out.println(sb.toString());
    }
 
    public static void main(String[] args)
    {
        List<Integer> heapTree = new ArrayList<Integer>();
        int delValue = 0;
 
        insertHeapTree(heapTree, 3);
        insertHeapTree(heapTree, 4);
        insertHeapTree(heapTree, 9);
        insertHeapTree(heapTree, 5);
        insertHeapTree(heapTree, 12);
        insertHeapTree(heapTree, 7);
        insertHeapTree(heapTree, 15);
        insertHeapTree(heapTree, 20);
 
        System.out.println(
            "HEAP DATA STRUCTURE - INSERT & DELETE OPERATION");
        System.out.println("Inserted Values in Heap-Tree");
        printArray(heapTree);
 
        Scanner sc = new Scanner(System.in);
        System.out.println(
            "Enter one value from above heap-tree values - to delete in Heap-Tree: ");
        delValue = sc.nextInt();
 
        deleteValue(heapTree, delValue);
        System.out.println("\nAfter deleting an element: ");
        printArray(heapTree);
    }
}

Python3

def swapping(x, y):
    # function to swap two numbers
    t = y
    y = x
    x = t
 
def insert_heap_tree(hT, val):
    # function to insert a value into the heap tree
    tree_size = len(hT)
    if tree_size == 0:
        hT.append(val)
    else:
        hT.append(val)
        i = tree_size
        while i != 0 and hT[i] > hT[(i - 1) // 2]:
            swapping(hT[i], hT[(i - 1) // 2])
            i = (i - 1) // 2
 
def delete_value(hT, val):
    # function to delete a value from the heap tree
    tree_size = len(hT)
    i = 0
    for i in range(tree_size):
        if val == hT[i]:
            break
    swapping(hT[i], hT[tree_size - 1])
    hT.pop()
 
def print_array(hT):
    # function to print the heap tree
    for i in range(len(hT)):
        print(hT[i], end=" ")
    print()
 
heap_tree = []
del_value = 0
insert_heap_tree(heap_tree, 3)
insert_heap_tree(heap_tree, 4)
insert_heap_tree(heap_tree, 9)
insert_heap_tree(heap_tree, 5)
insert_heap_tree(heap_tree, 12)
insert_heap_tree(heap_tree, 7)
insert_heap_tree(heap_tree, 15)
insert_heap_tree(heap_tree, 20)
print("HEAP DATA STRUCTURE - INSERT & DELETE OPERATION")
print("Inserted Values in Heap-Tree")
print_array(heap_tree)
del_value = int(input("Enter one value from above heap-tree values - to delete in Heap-Tree: "))
delete_value(heap_tree, del_value)
print("\nAfter deleting an element: ", end="")
print_array(heap_tree)

C#

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
 
// C# code implementation
class HelloWorld {
 
  public static void swapping(int x, int y)
  {
 
    // function to swap two numbers
    int t = y;
    y = x;
    x = t;
  }
  public static void insert_heap_tree(List<int> hT, int val) 
  {
 
    // function to insert a value into the heap tree
    int tree_size = hT.Count;
    if (tree_size == 0) {
      hT.Add(val);
    } 
    else {
      hT.Add(val);
      int i = tree_size;
      while (i != 0 && hT[i] > hT[(i - 1) / 2]) {
        swapping(hT[i], hT[(i - 1) / 2]);
        i = (i-1)/2;
      }
    }
  }
 
 
  public static void delete_value(List<int> hT, int val)
  {
     
    // function to delete a value from the heap tree
    if(hT.Count == 0) return;
 
    int tree_size = hT.Count;
    int i = 0;
    for (i = 0; i < tree_size; i++) {
      if (val == hT[i]) {
        break;
      }
    }
 
    if(i != hT.Count) swapping(hT[i], hT[tree_size - 1]);
    hT.RemoveAt(hT.Count-1);
  }
 
  public static void print_array(List<int> hT)
  { 
    string temp="";
     
    // function to print the heap tree
    for (int i = 0; i < hT.Count; i++) {
      temp = temp + hT[i] + " ";
    }
    Console.WriteLine(temp);
  }
 
  static void Main() {
    List<int> heap_tree = new List<int>();
    int del_value = 0;
    insert_heap_tree(heap_tree, 3);
    insert_heap_tree(heap_tree, 4);
    insert_heap_tree(heap_tree, 9);
    insert_heap_tree(heap_tree, 5);
    insert_heap_tree(heap_tree, 12);
    insert_heap_tree(heap_tree, 7);
    insert_heap_tree(heap_tree, 15);
    insert_heap_tree(heap_tree, 20);
 
    Console.WriteLine("HEAP DATA STRUCTURE - INSERT & DELETE OPERATION");
    Console.WriteLine("Inserted Values in Heap-Tree");
    print_array(heap_tree);
    Console.WriteLine("Enter one value from above heap-tree values - to delete in Heap-Tree: ");
    delete_value(heap_tree, del_value);
    Console.WriteLine("\nAfter deleting an element: ");
    print_array(heap_tree);
  }
}
 
// The code is contributed by Nidhi goel.

Javascript

//Javascript Equivalent
 
function swapping(x, y) {
    // function to swap two numbers
    let t = y;
    y = x;
    x = t;
}
 
function insert_heap_tree(hT, val) {
    // function to insert a value into the heap tree
    let tree_size = hT.length;
    if (tree_size == 0) {
        hT.push(val);
    } else {
        hT.push(val);
        let i = tree_size;
        for (let flr = Math.floor((i - 1) / 2); i != 0 && hT[i] > hT[flr]) {
            flr = Math.floor((i - 1) / 2);
            swapping(hT[i], hT[flr]);
            i = Math.floor((i - 1) / 2);
        }
    }
}
 
function delete_value(hT, val) {
    // function to delete a value from the heap tree
    let tree_size = hT.length;
    let i = 0;
    for (i = 0; i < tree_size; i++) {
        if (val == hT[i]) {
            break;
        }
    }
    swapping(hT[i], hT[tree_size - 1]);
    hT.pop();
}
 
function print_array(hT) { temp="";
    // function to print the heap tree
    for (let i = 0; i < hT.length; i++) {
    temp = temp + hT[i] + " ";
    }
    console.log(temp);
}
 
let heap_tree = [];
let del_value = 0;
insert_heap_tree(heap_tree, 3);
insert_heap_tree(heap_tree, 4);
insert_heap_tree(heap_tree, 9);
insert_heap_tree(heap_tree, 5);
insert_heap_tree(heap_tree, 12);
insert_heap_tree(heap_tree, 7);
insert_heap_tree(heap_tree, 15);
insert_heap_tree(heap_tree, 20);
console.log("HEAP DATA STRUCTURE - INSERT & DELETE OPERATION")
console.log("Inserted Values in Heap-Tree")
print_array(heap_tree);
console.log("Enter one value from above heap-tree values - to delete in Heap-Tree: ");
delete_value(heap_tree, del_value);
console.log("\nAfter deleting an element: ");
print_array(heap_tree);

Output

HEAP DATA STRUCTURE - INSERT & DELETE OPERATION
Inserted Values in Heap-Tree
3 4 9 5 12 7 15 20 
Enter one value from above heap-tree values -  to delete in Heap-Tree:  

After deleting an element: 3 4 9 5 12 7 15

Explanation: In the max-heap, every key node is larger than its child nodes, and the root key node is the greatest along with all the other nodes; in the min-heap, each key node is always smaller than their child nodes, and the root key node would be the smallest among the various other nodes.