A Brief Introduction to Heap in Data Structure

One of the concepts that we’ve spent a lot of time learning has been sorting. In this article, we will take a look at one of the simplest data structures that are very much used in all applications called the heap.

Introduction to Heap

A heap is a specialised tree-based data structure that is essentially an almost complete tree that satisfies the heap property in computer science. A heap has similar properties as a tree but with some additional ones.

The maximum number of children of a node in a heap depends on the type of heap. However, in the more commonly-used heap type, there are at most 2 children of a node and it’s known as a binary heap.

Put differently, a heap is a specialised tree-based data structure that satisfies specific heap properties. A heap has many applications, including the most efficient implementation of priority queues, useful in many applications. In particular, heaps are crucial in several efficient graph algorithms.

Binary Heap

A binary heap is a data structure, which looks similar to a complete binary tree. In a binary heap, the heap is said to be complete with N nodes and the possible height of the heap is log₂N. Heaps are not sorted. There is no particular relationship between nodes at any level. Binary heaps are usually implemented using arrays, which save the overhead cost of storing pointers to child nodes.

In the image above, every node has a greater value than any of its children. Suppose there are N jobs to be completed in a queue and the job is based on priority ordering. The job with the maximum priority will get completed first before others.

Heaps have specific ordering properties and is described below.

• Max-Heap: The value of each node is less than or equal to the value of the parent. The greatest value is at the root. The same property must be true for all subtrees.
  
  

• Min-Heap: The value of each node is greater than or equal to the value of its parent. The smallest value is at the root. The same property must be true for all subtrees.

A binary heap can also be represented as an array. Below are the 3 ways the data in a heap can be accessed from an array perspective.

Binomial Heap

The main application of Binary Heap is to implement the priority queue. Binomial Heap is an extension of Binary Heap that provides faster union or merge operation together with other operations provided by Binary Heap.

A Binomial Heap is a Binomial Tree collection where each Binomial Tree follows the Min-Heap property, and there can be at most one Binomial Tree of any degree.

A Binomial Tree must be represented in a way that allows sequential access to all siblings, starting from the leftmost sibling.

The idea is to represent Binomial Trees as the leftmost child and right-sibling representation where every node stores two pointers, one to the leftmost child and the other to the right sibling.

Differences between Binomial Heap and Binary Heap

The key difference between a Binary Heap and a Binomial Heap is how the heaps are structured internally. Let us take a look at the comparison table below to get a better understanding.

Applications of Heap

Heap is as simple as it sounds. It mostly involves navigating a tree from the root node to the children. Let us take a look at some of the most common applications of heap. Binary heaps are super-efficient for implementing priority queues because it’s very easy to know and retrieve/remove the element with the highest priority: it will always be the root node!

Priority Queue

Priority queues can be efficiently implemented using Binary Heap because it supports insert(), delete() and extractmax(), decreaseKey() operations in O(log_N) time.

Binomial Heap and Fibonacci Heap are variations of Binary Heap. These variations perform union also efficiently.

A typical Priority Queue requires following operations to be efficient.

• Get Top Priority Element (Get minimum or maximum)
• Insert an element
• Decrease Key
• Remove top priority element

Largest Element in an Array

Heap can be used alongside the popular algorithm called Bubble sort to find the largest element in an array. Instead of using temp[] array in a Bubble sort, use Min-Heap. We can build a Min-Heap of the first k elements (arr[0] to arr[k-1]) of the given array.

For each element, after the kth element (arr[k] to arr[n-1]), compare it with the root of Min-Heap. Below is the sample implementation in Python

def FirstKelements(arr,size,k):
	minHeap = []
	for i in range(k):
		minHeap.append(arr[i])
	# Loop For each element in array
	for i in range(k, size):
		minHeap.sort()
		if (minHeap[0] > arr[i]):
			continue
		else:
			minHeap.pop(0)
			minHeap.append(arr[i])
	for i in minHeap:
		print(i, end = " ")
arr=[11, 3, 2, 1, 15, 5, 4,45, 88, 96, 50, 45]
size = len(arr)
k=3
FirstKelements(arr, size, k)

Graph Algorithms

The priority queues are especially used in Graph Algorithms like Dijkstra’s Shortest Path and Prim’s Minimum Spanning Tree.

The algorithms mentioned above are some of the examples of a Greedy Algorithm. Greedy algorithms are basically algorithms that follow the problem-solving heuristic of making the locally optimal choice at each stage.

In many problems, a greedy strategy does not usually produce an optimal solution, but nonetheless, a greedy heuristic may yield locally optimal solutions that approximate a globally optimal solution in a reasonable amount of time.

Heap Sort

Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the minimum element and place the minimum element at the beginning. We repeat the same process for the remaining elements.

Heap Sort is a popular and efficient sorting algorithm in computer programming. Learning how to write the heap sort algorithm requires knowledge of two data structures – arrays and trees.

Heap Sort is not used much in practice but can be useful in real-time embedded systems where less space is available.

Conclusion

In summary, heaps are generally useful and easy to implement if we can understand the fundamentals of how trees, arrays work. All of this is one of the many examples of data structures.

To recap, a Heap is a binary data structure that is based on a tree. In computer science, a heap is a specialized tree-based data structure that is essentially an almost complete tree that satisfies the heap property.

Heaps have ordering properties such as min-heap and max-heap. A Binomial Heap is a Binomial Tree collection where each Binomial Tree follows the Min-Heap property, and there can be at most one Binomial Tree of any degree.

There are some notable differences between binary heaps and binomial heaps.

Related Posts