Heap Tree in Data Structure

A Heap Tree is a Complete Binary Tree and follows the Heap property. It always keeps either minimum or maximum values on top for priority access.

1. Introduction

A Heap can be either Min Heap or Max Heap.

• Min Heap: The parent node is always less than or equal to its children. So the smallest element is always kept at the root.
• Max Heap: In the case of Max Heap, the parent node is always greater than equal to its children. So the largest element is always kept on the root node for priority access.

Representation

// A vector can be used to represent the Heap
std::vector<int> heap;

// This is optional to have single implementation for both Min and Max Heap.
// A comparator to decide Min or Max heap
// Use std::greater for Max heap and std::less for Min heap
std::function<bool(int,int)> comp;

Applications

• Heaps are required if an application needs to access either minimum or maximum elements frequently.
• Priority Queue can be implemented using the heap. The high-priority node is always kept on the root and available in O(1) time.
• Heap sort is another popular use case.
• It can also be used to find the Kth smallest (or) Kth largest element of an array.

2. Insertion on Heap Tree

A node is always inserted in the last position of the tree followed by the Heapify operation. Heapify works upward after the insertion and compares the key against its parent. Swap the node with its parent if the heap property is not met. Repeat the same procedure until the node reaches its position.

Algorithm

1. Insert the new node at the last position.
2. Heapify the tree upward starting from the new node to the root.
3. Find the index of the parent node
4. Compare the node with its parent and check for the heap property.
   • Min Heap: The parent must be less than or equal (<=) to the child.
   • Max Heap: The parent must be greater than or equal (>=) to the child.
5. If the heap property is satisfied, stop the iteration and return.
6. Otherwise, swap the node with its parent and go to step 3.

Code

// Insert a new element
void Heap::insert(int data)
{
    // Insert the element at the last position
    heap.push_back(data);

    int i = (int) heap.size() - 1;
    int parent = ((1+i) / 2) - 1; // Find its parent index

    // Navigate from the last position to root via parent node
    // Compare current node with the parent to satisfy either min or max heap
    while (parent >= 0 && comp(heap[i], heap[parent])) {
        // Swap the elements to maintain the heap order
        swap(heap.at(i), heap.at(parent));

        // Repeat this process until it reaches the position.
        i = parent;
        parent = ((i+1) / 2) - 1;
    }
}

Example

The following diagrams illustrate the insertion of the data 40, 60, 30, 50, 20, and 10.

Insert element 40

Insert element 60

Insert element 30

Heapify to position the new node (30)

Insert element 50

Heapify to position the new node (50)

Insert element 20

Heapify to position the new node (20)

Insert element 10

Heapify to position the new node (10)

3. Deletion on Heap Tree

The heap has the highest priority element on the root node. The deletion algorithm focuses on deleting the root from the heap. The idea is to replace the root node with the last node and delete the last node. This can simplify the deletion but the tree often becomes non-heap. Hence perform the Heapify operation from the root node towards the bottom.

Algorithm

1. Check and return if the Heap is empty.
2. Replace the root node with the last node
3. Delete the last node
4. Heapify the tree down from the root node to the bottom of the tree.
   • Compare the node with its parent and check for the heap property.
     • Min Heap: The parent must be less than or equal (<=) to the child.
     • Max Heap: The parent must be greater than or equal (>=) to the child.
   • If not swap it with the appropriate child that has Min/Max value and repeat the Heapify for the affected child.
   • Otherwise, exit if the heap property is satisfied.

Code

// Remove the peek element
int Heap::remove()
{
    if (heap.size() == 0) {
        // Heap empty
        return -1;
    }

    // Replace the root node with the last element and delete the last
    int peek = heap[0];
    heap[0] = heap[heap.size()-1];
    heap.pop_back();

    // Heapify the root node so that it can rearrange the tree as per heap
    heapify(0);
    return peek;
}

// Heapify the tree by the given data
void Heap::heapify(int i)
{
    // Locate the indexes of it left and right child
    int parent = i;
    int left  = 2*parent + 1;
    int right = 2*parent + 2;
    
    // Check left child should be the parent as per heap property
    // For max heap, check if the left is greater than the parent
    // For min heap, check if the left is smaller than the parent
    if (left < heap.size() && comp(heap[left], heap[parent])) {
        parent = left;
    }
    
    // Check if the right child should be the parent
    if (right < heap.size() && comp(heap[right], heap[parent])) {
        parent = right;
    }

    // Swap elements if parent is changed and continue heapify
    // down the tree till the bottom.
    if (parent != i) {
        swap(heap.at(i), heap.at(parent));
        heapify(parent);
    }
}

Example

The following diagrams illustrate the deletion of the top two nodes.

Delete the root node (10)

Heapify down from the root node after removal

Delete the node (20)

Heapify the tree after removal

4. Build Heap from the Array

The initial heap can be built from an array of elements for various requirements. One way is to create an empty Heap and insert the elements one by one by iterating the Array. This method is called Williams’ method after the inventor of the Binary Heap and takes O(n log n) time. However, a faster method introduced by Floyd works in O(n) time.

Put the arbitrary elements in an array and Heapify the nodes from the bottom of the tree. Start from the last non-leaf node and run Heapify for all the prior nodes until it reaches the root.

Algorithm

1. Put the arbitrary elements in an array.
2. Find the index of the last non-leaf node (size/2 – 1).
3. Iterate from the last non-leaf node to the root and run the Heapify operation for each node.
   • Compare the node with its children and check if satisfy the heap property.
     • Min Heap: The parent must be less than or equal (<=) to the child.
     • Max Heap: The parent must be greater than or equal (>=) to the child.
   • If not swap it with the appropriate child that has Min/Max value and repeat the Heapify for the affected child.

Code

// Create the heap from an array of elements
void Heap::build_heap(int data[], int size)
{
    // Replace the heap data
    heap.assign(data, data+size);

    // Start heapify from the last non leaf node to root
    int non_leaf = (size / 2) - 1;
    for (int i=non_leaf; i >= 0; --i) {
        heapify(i);
    }
}

Example

Sample Array represented as Binary Tree

Build the Max Heap from the Array

Next, Heapify the node (60). Here, the right child (70) is greater and requires a swap operation.

Next, Heapify the root node (40). Here, both of its children (70) and (40) are greater and violate the Max Heap. Choose the largest child (70) and swap with the parent. Proceed to Heapify down the affected child which still violates Max Heap. Hence swap (40) with its largest child (60).

5. Traversals on Heap Tree

See Traversals on Binary Tree that are applicable for the Heap Tree.

6. Implementation of Heap Tree in C++

/**
 * C++ example to demonstrate the Heap
 */
#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
using namespace std;

/**
 * Heap implementation
 */
class Heap
{
    // Heap
    std::vector<int> heap;

    // Comparator to decide min or max heap
    // Use std::greater for max heap and std::less for min heap
    std::function<bool(int,int)> comp;

public:
    // Constructor
    Heap(std::function<bool(int,int)> comp) : comp(comp) {}

    // Create the heap from an array of elements
    void build_heap(int data[], int size);

    // Heapify the tree from the given node
    void heapify(int i);

    // Insert a new element
    void insert(int data);

    // Delete the peek element and return the data
    int remove();

    // Print the heap
    int print(std::string label = "");
};

// Create the heap from an array of elements
void Heap::build_heap(int data[], int size)
{
    // Replace the heap data
    heap.assign(data, data+size);

    // Start heapify from the last non leaf node to root
    int non_leaf = (size / 2) - 1;
    for (int i=non_leaf; i >= 0; --i) {
        heapify(i);
    }
}

// Heapify the tree by the given data
void Heap::heapify(int i)
{
    // Locate the indexes of it left and right child
    int parent = i;
    int left  = 2*parent + 1;
    int right = 2*parent + 2;
    
    // Check left child should be the parent as per heap property
    // For max heap, check if the left is greater than the parent
    // For min heap, check if the left is smaller than the parent
    if (left < heap.size() && comp(heap[left], heap[parent])) {
        parent = left;
    }
    
    // Check if the right child should be the parent
    if (right < heap.size() && comp(heap[right], heap[parent])) {
        parent = right;
    }

    // Swap elements if parent is changed and continue heapify
    // down the tree till the bottom.
    if (parent != i) {
        swap(heap.at(i), heap.at(parent));
        heapify(parent);
    }
}

// Insert a new element
void Heap::insert(int data)
{
    // Insert the element at the last position
    heap.push_back(data);

    int i = (int) heap.size() - 1;
    int parent = ((1+i) / 2) - 1; // Find its parent index

    // Navigate from the last position to root via parent node
    // Compare current node with the parent to satisfy either min or max heap
    while (parent >= 0 && comp(heap[i], heap[parent])) {
        // Swap the elements to maintain the heap order
        swap(heap.at(i), heap.at(parent));

        // Repeat this process until it reaches the position.
        i = parent;
        parent = ((i+1) / 2) - 1;
    }
}

// Remove the peek element
int Heap::remove()
{
    if (heap.size() == 0) {
        // Heap empty
        return -1;
    }

    // Replace the root node with the last element and delete the last
    int peek = heap[0];
    heap[0] = heap[heap.size()-1];
    heap.pop_back();

    // Heapify the root node so that it can rearrange the tree as per heap
    heapify(0);
    return peek;
}

// Print the heap
int Heap::print(std::string label)
{
    // Print label if provided
    if (! label.empty()) {
        cout << label << endl;
    }

    // Print heap elements as per array order
    for (auto d: heap) {
        cout << d << " ";
    }
    cout << endl;
}

int main()
{
    // Create a Min heap and insert elements
    Heap min_heap(std::less<>{});
    min_heap.insert(40);
    min_heap.insert(60);
    min_heap.insert(30);
    min_heap.insert(50);
    min_heap.insert(20);
    min_heap.insert(10);
    min_heap.print("Min heap after inserting 40, 60, 30, 50, 20, and 10");

    // Remove elements
    min_heap.remove();
    min_heap.remove();
    min_heap.print("Heap after removing couple of peek elements");

    // Create a Max Heap from the array of elements
    Heap max_heap(std::greater<>{});
    int data[] = {40, 60, 50, 30, 70, 20, 10};
    max_heap.build_heap(data, sizeof(data) / sizeof(data[0]));
    max_heap.print("Max heap built from the array {40, 60, 50, 30, 70, 20, 10}");
}

Output

Min heap after inserting 40, 60, 30, 50, 20, and 10
10 30 20 60 50 40 
Heap after removing couple of peek elements
30 50 40 60 
Max heap built from the array {40, 60, 50, 30, 70, 20, 10}
70 60 50 30 40 20 10

7. References

• Binary Heap Wiki