Heap Data Structure: What is Heap?

What is a Heap Data Structure?

A Heap is a specialized tree-based data structure. The Heap Data Structure comprises a topmost node called the root (parent). Its second node is the root’s left child, while the third node is the root’s right child. The successive nodes are filled from left to right. The parent-node key compares to that of its offspring so that a proper arrangement occurs. The tree is easy to visualize where each entity is called a node, and every node has a unique key for identification.

In simple terms, a Heap is a complete binary tree that satisfies the heap property: every parent is ordered consistently against its children, which makes it ideal for priority queues and Heap Sort.

Why do you need Heap Data Structure?

Here are the main reasons for using a Heap:

• The Heap Data Structure allows deletion and insertion in logarithmic time – O(log₂n).
• The data in the tree is arranged in a particular order. Besides updating or querying values such as a maximum or minimum, the programmer can find relationships between the parent and the offspring.
• You can apply the concept of the Document Object Model to help you understand the Heap Data Structure visually.
• Heaps support efficient priority queue operations, which are critical for graph algorithms such as Dijkstra’s shortest path and Prim’s minimum spanning tree.

Types of Heaps

Heap Data Structure has various algorithms for handling insertions and removing elements, including Priority Queue, Binary Heap, Binomial Heap, and Heap Sort.

• Priority Queue: It is an abstract data structure containing prioritized objects. Each object or item has a priority pre-arranged for it. Therefore, the object or item assigned the higher priority gets the service before the rest.
• Binary Heap: Binary heaps are suitable for simple heap operations such as deletions and insertions. They are the default implementation behind most standard library priority queues.
• Binomial Heap: A Binomial Heap consists of a series of collections of binomial trees that make up the heap. A Binomial Heap tree is no ordinary tree as it is rigorously defined. The total number of elements in a binomial tree always equals 2ⁿ nodes.
• Heap Sort: Unlike most sorting algorithms, Heap Sort uses O(1) space for its sort operation. It is a comparison-based sorting algorithm where sorting occurs in increasing order by first turning the input into a Max-Heap. You can look at Heap Sort as an upgraded binary search tree.

Typically, a Heap Data Structure employs two strategies. For input 12 – 8 – 4 – 2 and 1:

• Min-Heap – least value at the top
• Max-Heap – highest value at the top

Min-Heap

In the Min-Heap structure, the root node has a value either equal to or smaller than the children of that node. The root of a Min-Heap therefore holds the minimum value. The Min-Heap is also a complete binary tree.

Once you have a Min-Heap in a tree, all the leaves are viable candidates for the maximum value. However, you need to examine each leaf in order to get the exact Max-Heap value.

Min-Heap Example

In the diagram above, you can notice a clear sequence from the root to the lowest node.

Suppose you store the elements in array Array_N[12, 2, 8, 1, 4]. As you can see from the array, the root element is violating the Min-Heap priority. To maintain the Min-Heap property, you have to perform the min-heapify operations to swap the elements until the Min-Heap rules are met.

Max-Heap

In the Max-Heap structure, the parent or root node has a value equal to or larger than its children. This node holds the maximum value. It is a complete binary tree, so you can build a Max-Heap from a collection of values in O(n) time.

Here are a few methods commonly used when implementing a Java Max-Heap:

• Add (): Places a new element into a heap. If you use an array, the objects are added at the end of the array, while in the binary tree, the objects are added from top to bottom and then from left to right.
• Remove (): This method allows you to remove the first element from the array list. As the newly promoted element is no longer the largest, the Sift-Down method always pushes it to its new location.
• Sift-Down (): This method compares a root object to its children and then pushes the relocated node to its rightful position.
• Sift-Up (): If you use the array method to add a newly inserted element to an array, then the Sift-Up method helps the newly added node relocate to its correct position. The new item is first compared to its parent by simulating the tree data structure.

  Apply the formula Parent_Index = Child_Index / 2. You continue doing this until the maximum element is at the front of the array.

Basic Heap Operations

For you to find the highest and lowest values in a set of data, you need a few basic heap operations such as find, insert, and delete. Because elements constantly come and go, you should know how to:

• Find – Look for an item in a heap.
• Insert – Add a new child into the heap.
• Delete – Delete a node from a heap.

Create Heaps

The process of constructing heaps is known as creating heaps. Given a list of keys, the programmer makes an empty heap and then inserts the other keys one at a time using the basic heap operations.

So let us begin building a Min-Heap using William’s method by inserting the values 12, 2, 8, 1, and 4. You can build the heap with n elements by starting with an empty heap and then filling it successively with other elements using O(n log n) time.

• Heapify: An insertion routine that helps insert elements into a heap while preserving the heap property.

  For instance, a max-heapify operation checks that the value of the parent is greater than its offspring. The elements can then be sorted using methods like swapping.

• Merge: When you have two heaps to combine into one, use the merge operation to bring the values from the two heaps together. The original heaps are still preserved.

Inspect Heaps

Inspecting heaps refers to checking the number of elements in the Heap Data Structure and validating whether the heap is empty.

It is important to inspect heaps while sorting or queueing elements. Checking that there are elements to process using Is-Empty() is important. The heap size will help locate the Max-Heap or Min-Heap roots, so you need to know how many elements follow the heap property.

• Size – returns the magnitude or length of the heap. It tells you how many elements are stored in sorted order.
• Is-Empty – returns TRUE if the heap is null, otherwise it returns FALSE.

Here, you are printing all elements in the priorityQ loop and then checking that priorityQ is not empty.

//print head the head values
       While (!priorityQ.isEmpty()) {
        System.out.print(priorityQ.poll()+" ");

Uses of Heap Data Structure

Heap Data Structure is useful in many programming applications in real life, such as:

• Helps in spam filtering.
• Implementing graph algorithms such as Dijkstra and Prim.
• Operating system load balancing and data compression.
• Finding order statistics such as the k-th smallest element.
• Implementing priority queues where you can search items in a list in logarithmic time.
• Heap Data Structure is also used for sorting through Heap Sort.
• Simulating customers in a waiting line.
• Interrupt handling in the Operating System.
• In Huffman coding for data compression.
• Powering best-first search and A* heuristics in AI path planning.

Heap Priority Queue Properties

The following properties describe how the priority queue built on a heap behaves:

• In priority heaps, the data items in the list are compared to each other to determine the smaller or larger element.
• An element is placed in a queue and afterward removed in priority order.
• Every single element in the priority queue has a unique number related to it identified as a priority.
• Upon exiting a priority queue, the top-priority element exits first.

Steps for Implementing the Heap Priority Queue in Java

The next section moves into a concrete Java implementation that turns these rules into working code.

Heap Sort in Java with Code Example

import java.util.Arrays;
public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {5, 9, 3, 1, 8, 6};
        // Sort the array using heap sort
        heapSort(arr);
        // Print the sorted array
        System.out.println(Arrays.toString(arr));
    }
    public static void heapSort(int[] arr) {
        // Convert the array into a heap
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            heapify(arr, arr.length, i);
        }
        // Extract the maximum element from the heap and place it at the end of the array
        for (int i = arr.length - 1; i >= 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // Find the largest element among the root, left child, and right child
        if (left < n && arr[left] > arr[largest]) {
            largest = left;
        }
        if (right < n && arr[right] > arr[largest]) {
            largest = right;
        }
        // If the largest element is not the root, swap and heapify the sub-tree
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}

Output

Original Array:

5 9 3 1 8 6

Heap after insertion:

9 8 6 1 5 3

Heap after sorting:

1 3 5 6 8 9

Heap Sort in Python with Code Example

def heap_sort(arr):
    """
    Sorts an array in ascending order using heap sort algorithm.
    Parameters:
        arr (list): The array to be sorted.
    Returns:
        list: The sorted array.
    """
    n = len(arr)
    # Build a max heap from the array
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # Extract elements from the heap one by one
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]  # swap the root with the last element
        heapify(arr, i, 0)  # heapify the reduced heap
    return arr
def heapify(arr, n, i):
    """
    Heapifies a subtree with the root at index i in the given array.
    Parameters:
        arr (list): The array containing the subtree to be heapified.
        n (int): The size of the subtree.
        i (int): The root index of the subtree.
    """
    largest = i  # initialize largest as the root
    left = 2 * i + 1  # left child index
    right = 2 * i + 2  # right child index
    # If left child is larger than root
    if left < n and arr[left] > arr[largest]:
        largest = left
    # If right child is larger than largest so far
    if right < n and arr[right] > arr[largest]:
        largest = right
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = (
            arr[largest],
            arr[i],
        )  # swap the root with the largest element
        heapify(arr, n, largest)  # recursively heapify the affected subtree
arr = [4, 1, 3, 9, 7]
sorted_arr = heap_sort(arr)
print(sorted_arr)

Output

[1, 3, 4, 7, 9]

Next, you will learn about the Bisection Method.

FAQs