What is Heap in Data Structure?

Last Updated on September 22, 2023 by Mayank Dham

In this article, we will study about heap data structure wherein the theory, concept and implementation will be discussed in the many sections of this article on heap data structure.
Moreover, We will study heap sort and how the heap sort algorithm works on a heap tree. By the end of the article, we will have clarity on the topic to solve complex problems related to heap data structure.

What is Heap Data structure?

Heap Data Structure is also known as Binary Heap that is in the form of a tree and follows the property of a complete binary tree such that all the levels of the tree are filled by nodes except the last level, that can be partially filled.

Although it is represented in the form of a tree, it is stored in the memory as an array unlike a tree that is obtained through referring to child nodes. As the elements are stored contiguously in an array, it is more cache-friendly while the complete binary tree ensures that there are the least number of tree levels possible for total elements.

The following mathematical formula can help us find the left child and right child or a tree or even the parent in the array.

Here, i, means index such that if we want any such relationship, we can substitute the value of the index and find out our necessary requirements easily.

Now that we have an idea on what is heap in data structure, we move on looking at the use cases of heap data structure. Heap data structure is used to implement priority queues in problem-solving while it is extensively used in heap sort which will be covered in the further sections alongside heap sort algorithm.

Types of Heap in Data Structure

Now that we have some general understanding of heap data structure, there are two types of heap which can be classified as:-

1. Min Heap :- The smallest element is present at the root of the tree in the min heap such that it is easier to extract the smallest element when heap pop is performed.

2. Max Heap :- The greatest element is present at the root of the tree in the max heap such that it is easier to extract the largest element when heap pop is performed.

The illustration stating the both is represented below:

Heap Sort

Heap Sort is an efficient optimization of selection sort algorithm where one element is placed at its rightful position and we further in array to sort the respective elements left. Firstly, in heap sort, we must have max heap available at our disposal so he starts by building a max heap in heap sort.

This can be understood more precisely using heap sort dry run and heap sort algorithm.

Dry Run of Heap Sort Algorithm

Looking at the heap tree above, we will trace step by step on how heap sort works to sort the array. First the swapping will be made where 35 moves to the last index and vice versa and heapify operation is performed.

With 35 being removed from the heap tree, we perform the second largest element for index 3 now.

Next step in heap sort dry run, we swap 13 with 10 and reduce the size to heapify, thus obtaining the sorted array.

Thus, removing 10, we will be left with a lone node in the heap tree indicating the successful implementation of the heap sort algorithm.

Having seen the heap sort dry run, we have a brighter picture on what heap sort is. Now let us have look at the algorithm of heap sort.

Heap Sort Algorithm

Heap sort algorithm can be demonstrated as follows with the use of heapify property and storing of elements.

1. Build a max heap
2. for each element in array
   1. Swap root element with last element
   2. Heapify the array
   3. Decrement array size by 1
3. Print the array

Code Implementation

def heapify(nums, N, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < N and nums[largest] < nums[left]:
        largest = left
    if right < N and nums[largest] < nums[right]:
        largest = right
    if largest != i:
        nums[i], nums[largest] = nums[largest], nums[i]
        heapify(nums, N, largest)

def heapSort(nums):
    N = len(nums)
    for i in range(N//2 - 1, -1, -1):
        heapify(nums, N, i)
    for i in range(N-1, 0, -1):
        nums[i], nums[0] = nums[0], nums[i]
        heapify(nums, i, 0)

nums = [35,32,10,5,3]
heapSort(nums)
print(nums)

Output

[3, 5, 10, 32, 35]

Heap Sort Time and Space Complexity:

Heap Sort takes worst-case complexity of O(n*log(n)) where n denotes the total elements of the array that are placed at their respective positions while the log(n) denotes the heapify process.

As there is no extra space used, the space complexity remains to be O(1) i.e constant time.

More about Heap Sort

The heap sort algorithm is not a stable sort algorithm as relative ordering of the element is changed.

Heap Sort algorithm is divided into two parts where the first one being making a max heap and second being the heapify process to sort the array.

Conclusion
In this article, we studied about the introduction of binary heaps and what is heap in data structure and proceeded in further sections to know about the use cases of heap data structure, its types and the use cases.

What is Heap Sort and Heap Sort Algorithm was the key takings from this article as we understood the working using a heap tree along with code and its space and time complexity. We hope you liked this article focused on heap data structure and heap sort and expect to see you again at PrepBytes with another piece of insightful information

Frequently Asked Questions – Heap Data Structure

1. What are the two types of heap?
Ans. The two main types of heap data structure are min heap and max heap.

2. Which is faster merge sort or heap sort?
Ans. Merge sort is faster than heap sort due to less calculations but it consumes extra space which is not the case with heap sort.

3. What is the worst case time complexity of heap sort?
Ans. The worst case complexity of heap sort is O(NlogN).