Introduction to Heap Data Structure

Level - Medium

What is Heap Data Structure ?

A heap is a specialized tree-based data structure that satisfies the heap property. In a heap, each parent node has a value greater than or equal to its child nodes (for max-heap) or less than or equal to its child nodes (for min-heap).

Types of Heap Data Structures

Max-Heap

In a max-heap, the value of each parent node is greater than or equal to the values of its child nodes.

Example:

Min-Heap

In a min-heap, the value of each parent node is less than or equal to the values of its child nodes.

Example:

Properties of Heap Data Structure

1. Heap Property: The heap property is a fundamental characteristic of heaps that governs the order of elements. There are two variations:
   • Max-Heap: In a max-heap, the value of each parent node is greater than or equal to the values of its child nodes. This ensures that the element with the highest value is positioned at the root. Max-heaps are useful for applications like priority queues, where you need quick access to the maximum element.
   • Min-Heap: In a min-heap, the value of each parent node is less than or equal to the values of its child nodes. This results in the minimum element being located at the root. Min-heaps are valuable in scenarios such as priority queues for finding the minimum element efficiently.
2. Complete Binary Tree: Heaps are organized as complete binary trees.

Detailed Explaination of Complete Binary Tree

Before we understand that what is Complete Binary Tree we should know about array representation of binary tree.

Array Representation of Binary Tree

What is Complete Binary Tree ?

Definition: A complete binary tree is a special type of binary tree where all levels of the tree are completely filled except possibly for the last level, which is filled from left to right. In other words, a complete binary tree is a binary tree in which all nodes are as left as possible, leaving no "gaps" between nodes at the same level.

so above is the defination which is common on internet but for simple understanding we can say Complete Binary Tree is the tree which when represented as array should not have any null values in array.

Knowledge check

Loading...

Heap Operations

Heaps support various operations to efficiently manage elements while maintaining their properties.

1. push(int element): This operation inserts the given element into the heap while maintaining the heap property. The element is placed at an appropriate position based on its value relative to the parent and child nodes.
2. peek(): The peek operation retrieves the top (root) element of the heap without removing it. It provides access to the highest (max-heap) or lowest (min-heap) priority element.
3. remove(): The remove operation removes and returns the top element from the heap. After removal, the heap property is restored by adjusting the remaining elements to maintain the proper order.
4. isEmpty(): This operation determines whether the heap is empty or not. It returns true if the heap contains no elements, and false otherwise.

Heapify Step

Heapify is a crucial step used internally by the push and remove operations to ensure the heap properties are satisfied. Heapify involves comparing a node's value with its children and possibly swapping them to maintain Heap Properties.

Problem Statement

Implement the Heap class with 4 operations and note you have to Implement Max Heap:

1. push(int element)
2. remove()
3. peek()
4. isEmpty()

Visual Walkthrough Heap push operation:

Visual Walkthrough Heap remove operation:

Implementation of Heap Operations

Java

 import java.utils.*;
 class Heap {
   // this is "max heap"
   int n = 0;
   ArrayList < Integer > tree;
   Heap() {
     tree = new ArrayList < Integer > ();
   }
   void heapify(int index) {
     int right_child_index = 2 * index + 1;
     int left_child_index = 2 * index + 2;
     int largest_index = index;
     // select who is largest among current node , left child node and right child node
     if (left_child_index < n && tree.get(left_child_index) > tree.get(largest_index)) largest_index = left_child_index;
     if (right_child_index < n && tree.get(right_child_index) > tree.get(largest_index)) largest_index = right_child_index;
     // if current element is smaller so swap current with larger child and move in that direction
     if (largest_index != index) {
       swap(index, largest_index);
       heapify(largest_index);
     }
   }
   void push(int element) {
     // add new element in last of array/tree
     tree.add(element);
     n++;
     // compare all the nodes from new node towards root node to satisfy heap property
     int element_index = n - 1;
     int parent_node_index = (element_index - 1) / 2;
     while (element_index > 0 && tree.get(element_index) > tree.get(parent_node_index)) {
      swap(element_index, parent_node_index);
      element_index = parent_node_index;
      parent_node_index = (element_index - 1) / 2;
    }
   }
   int remove() {
     // swap root node with last node, reduce the size by 1  
     swap(0, n - 1);
     int last_node = tree.get(n - 1);
     n--;
     // perform heapify as after swap heap property is destroyed
     heapify(0);
     return last_node;
   }
   boolean isEmpty() {
     return n == 0;
   }
   int peek() {
     if (isEmpty()) return -1;
     else
       return tree.get(0);
   }
   void swap(int index1, int index2) {
     int temp = tree.get(index1);
     tree.set(index1, tree.get(index2));
     tree.set(index2, temp);
   }
 }

CPP

#include <vector>

class Heap {
public:
    int n;
    std::vector<int> tree;
    Heap() {
        n = 0;
    }

    void heapify(int index) {
        int right_child_index = 2 * index + 1;
        int left_child_index = 2 * index + 2;
        int largest_index = index;
        // select who is largest among current node , left child node and right child node
        if (left_child_index < n && tree[left_child_index] > tree[largest_index])
            largest_index = left_child_index;
        if (right_child_index < n && tree[right_child_index] > tree[largest_index])
            largest_index = right_child_index;
        // if current element is smaller so swap current with larger child and move in that direction
        if (largest_index != index) {
            swap(index, largest_index);
            heapify(largest_index);
        }
    }

    void push(int element) {
        // add new element in heap
        tree.push_back(element);
        n++;

        int element_index = n - 1;
        int parent_node_index = (element_index - 1) / 2;
        // compare all the nodes from new node towards root node to satisfy heap property
        while (element_index > 0 && tree[element_index] > tree[parent_node_index]) {
            swap(element_index, parent_node_index);
            element_index = parent_node_index;
            parent_node_index = (element_index - 1) / 2;
        }
    }

    int remove() {
        // swap root node with last node, reduce the size by 1
        swap(0, n - 1);
        int last_node = tree[n - 1];
        n--;
        // perform heapify as heap property is destroyed after swap
        heapify(0);
        return last_node;
    }

    bool isEmpty() {
        return n == 0;
    }

    int peek() {
        if (isEmpty())
            return -1;
        else
            return tree[0];
    }

    void swap(int index1, int index2) {
        int temp = tree[index1];
        tree[index1] = tree[index2];
        tree[index2] = temp;
    }
};

Python

class Heap:
    def __init__(self):
        # this is max heap
        self.n = 0
        self.tree = []

    def heapify(self, index):
        # Calculate the indices of the left and right children
        right_child_index = 2 * index + 1
        left_child_index = 2 * index + 2
        largest_index = index

        # Select the index of the largest element among the current node, left child, and right child
        if left_child_index < self.n and self.tree[left_child_index] > self.tree[largest_index]:
            largest_index = left_child_index
        if right_child_index < self.n and self.tree[right_child_index] > self.tree[largest_index]:
            largest_index = right_child_index

        # If the largest element is not the current node, swap and recursively heapify
        if largest_index != index:
            self.swap(index, largest_index)
            self.heapify(largest_index)

    def push(self, element):
        # Add the new element to the end of the tree
        self.tree.append(element)
        self.n += 1

        element_index = self.n - 1
        parent_node_index = (element_index - 1) // 2

        # Compare all the nodes from the new node towards the root node to satisfy the heap property
        while element_index > 0 and self.tree[element_index] > self.tree[parent_node_index]:
            self.swap(element_index, parent_node_index)
            element_index = parent_node_index
            parent_node_index = (element_index - 1) // 2

    def remove(self):
        # Swap the root node with the last node and reduce the size by 1
        self.swap(0, self.n - 1)
        last_node = self.tree[self.n-1]
        self.n -= 1

        # Perform heapify as after swap the heap property is destroyed
        self.heapify(0)
        return last_node

    def is_empty(self):
        return self.n == 0

    def peek(self):
        if self.is_empty():
            return -1
        else:
            return self.tree[0]

    def swap(self, index1, index2):
        self.tree[index1], self.tree[index2] = self.tree[index2], self.tree[index1]

Use Heap Class to perform below Queries

Example Queries

init empty heap array
push(4) // insert the element in heap array
push(1) // insert the element in heap array
peek() // return 4
push(3) // insert the element in heap array
push(9) // insert the element in heap array
peek() // return 9
push(7) // insert the element in heap array
remove() // return 9
remove() // return 7
remove() // return 4
remove() // return 3
remove() // return 1
print heap array // 1 , 3 , 4 , 7 , 9 

Java

class Main{
    public static void main(String args[]){
      Heap heap = new Heap(); // init heap
      heap.push(4);
      heap.push(1);
      System.out.println("peek: "+heap.peek());
      heap.push(3);
      heap.push(9);
      System.out.println("peek: "+heap.peek());
      heap.push(7);
      System.out.println("removed: "+heap.remove());
      System.out.println("removed: "+heap.remove());
      System.out.println("removed: "+heap.remove());
      System.out.println("removed: "+heap.remove());
      System.out.println("removed: "+heap.remove());
      System.out.println(heap.tree);
    } 
}

CPP

#include <iostream>
int main() {
    Heap heap; // Initialize the heap
    heap.push(4);
    heap.push(1);
    std::cout << "peek: " << heap.peek() << std::endl;
    heap.push(3);
    heap.push(9);
    std::cout << "peek: " << heap.peek() << std::endl;
    heap.push(7);
    std::cout << "removed: " << heap.remove() << std::endl;
    std::cout << "removed: " << heap.remove() << std::endl;
    std::cout << "removed: " << heap.remove() << std::endl;
    std::cout << "removed: " << heap.remove() << std::endl;
    std::cout << "removed: " << heap.remove() << std::endl;
    for (int value : heap.tree)std::cout << value << ' ';
    std::cout << std::endl;
    
    return 0;
}

Python

heap = Heap()  # Initialize the heap
heap.push(4)
heap.push(1)
print("peek:", heap.peek())
heap.push(3)
heap.push(9)
print("peek:", heap.peek())
heap.push(7)
print("removed:", heap.remove())
print("removed:", heap.remove())
print("removed:", heap.remove())
print("removed:", heap.remove())
print("removed:", heap.remove())
print(heap.tree)

Output: 

peek: 4
peek: 9
removed: 9
removed: 7
removed: 4
removed: 3
removed: 1
[1, 3, 4, 7, 9]

Complexity

log(N) is complexity of insert function as well as delete function.