Heap Data Structure: What is Heap? Min & Max Heap (Example)
Alyssa Walker
What is a Heap?
Heap is a specialized tree data structure. The heap comprises the topmost node called a root (parent). Its second child 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, and a proper arrangement occurs. The tree is easy to visualize where each entity is called a node. The node has unique keys for identification.
Why do you need Heap Data Structure?
Here are the main reasons for using Heap Data Structure:
- The heap data structure allows deletion and insertion in logarithmic time – O(log2n).
- The data in the tree is fashioned in a particular order. Besides updating or querying things 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 assist you in understanding the heap data structure.
Types of Heaps
Heap data structure has various algorithms for handling insertions and removing elements in a heap data structure, 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 higher priority is getting the service before the rest.
- Binary-Heap: Binary heaps are suitable for simple heap operations such as deletions and insertions.
- Binomial-Heap: A binomial heap consists of a series of collections of binomial trees that make up the heap. Binomial Heap tree is no ordinary tree as it is rigorously defined. The total number of elements in a binomial tree always possess 2n nodes.
- Heap-Sort: Unlike most sorting algorithms, heap-sort uses O(1) space for its sort operation. It’s a comparison-based sorting algorithm where sorting occurs in increasing order by first turning it into a max heap. You can look at a Heapsort as an upgraded quality 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 on that node. This heap node of a Min Heap holds the minimum value. All in all, its min-heap structure is a complete binary tree.
Once you have a Min heap in a tree, all the leaves are viable candidates. However, you need to examine each of the leaves in order to get the exact Max-heap value.
Min Heap Example
In the diagrams above, you can notice some 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 properties are met.
Max Heap
In Max Heap’s structure, the parent or root node has a value equal to or larger than its children in the node. This node holds the maximum value. Moreover, it’s a complete binary tree, so you can build a max heap from a collection of values and run it on O(n) time.
Here are a few methods for implementing a java max heap
- Add (): place 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 after left to right.
- Remove (): This method allows you to remove the first element from the array list. As the newly added 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 child and then pushes the newly added 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 new position. The newly inserted item is first compared to the parent by simulating the tree data structure.
Apply 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 lots of basic heap operations such as find, delete, and insert. Because elements will constantly come and go, you have 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 other keys one at a time using basic heap operations.
So let’s begin building a Min-heap using Willaim’s method by inserting values 12,2,8,1 and 4 in a heap. You can build the heap with n elements by starting with an empty heap and then filling it successively with other elements using O (nlogn) time.
- Heapify: in insertion algorithm, which helps insert elements into a heap. Checks, whether the property heap data structure highlighted, are followed.
For instance, a max heapify would check if the value of the parent is greater than its offspring. The elements can then be sorted using methods like swapping.
- Merge: Considering you have two heaps to combine into one, use merge heaps to bring the values from the two heaps together. However, 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 as sorting or queueing of elements. Checking if you have elements to process using Is-Empty() is important. The heap size will help locate the max-heap or min-heap. So, you need to know the elements following the heap property.
- Size – returns the magnitude or length of the heap. You can tell how many elements are in sorted order.
- Is-empty – if the heap is NULL, it returns TRUE 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 like:
- Helps in Spam Filtering.
- Implementing graph algorithms.
- Operating System load balancing, and data compression.
- Find the order in the statistics.
- Implement Priority queues where you can search for items in a list in logarithmic time.
- Heap data structure also use for sorting.
- Simulating customers on a line.
- Interrupt handling in Operating System.
- In Huffman’s coding for data compression.
Heap Priority Queue Properties
- In priority heaps, the data items in the list are compared to each other to determine the smaller element.
- An element is placed in a queue and afterward removed.
- 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
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 the root and the largest element 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’ll learn about Bisection Method
Summary
- Heap is a specialized tree data structure. Let’s imagine a family tree with its parents and children.
- The heaps data structure in Java allows deletion and insertion in logarithmic time – O(log2n).
- Heaps in Python has various algorithms for handling insertions and removing elements in a heap data structure, including Priority-Queue, Binary-Heap, Binomial Heap, and Heapsort.
- In the Min Heap structure, the root node has a value equal to or smaller than the children on that node.
- In Max Heap’s structure, the root node (parent) has a value equal to or larger than its children in the node.
- Inspecting Heaps refers to checking the number of elements in the heap data structure and validating whether the heap is empty.