### Min Priority Queue Implementation with Heap Data structure

Min Priority Queue is a data structure which manage a list of keys(values). And…

July 03, 2019

Its a tree based data structure which is a complete binary tree(all nodes have 2 nodes, leaf-child may not have all 2), and satisfies a heap property. But, the amazing thing is that it uses array as its underlying data structure.

The heap is the implementation of the Priority Queue, where top most priority (or lowest priority) element is required to be at the top.

In this tree representation, every root node is always greater than both of its child. Note: right child can be lesser than left child.

As reverse of the max heap. Every root element is always smaller than both of its child elements.

Some basic operations on heap are:

- heapify - To maintain either max or min heap property.
- findMax or findMin - To get the top element of heap
- insertElement - To insert a new element to the heap
- extractMax or extractMin - Delete the top element, and return it
- Get heapsize - Get the heap size
- Increment/Decrement - For incrementing or decrementing priority or value of any node

As I said earlier, they are based on array, not on any pointers stuff. Consider an array:

`224,131,23,45,52,287,304,122,460,438`

The first element will be the root of tree, 2nd and 3rd are the child of it. 4th and 5th will be child of 2nd node. And so on.

```
224
/ \
131 23
/ \ / \
45 52 287 304
/ \ /
122 460 438
```

Note: Above is just tree representation from array. It does not satisfy any max-heap or min-heap property.

`leftChildIndex = rootIndex * 2 + 1`

`rightChildIndex = rootIndex * 2 + 2`

Lets assume we have to build a max heap. We would want every root node to be greater than its child nodes.

```
void max_heapify(int[] arr, int index, int heapsize) {
int l = 2 * index + 1;
int r = 2 * index + 2;
int indexOfLargest = index;
if (l < heapsize && arr[l] > arr[index]) {
indexOfLargest = l;
}
if (r < heapsize && arr[r] > arr[indexOfLargest]) {
indexOfLargest = r;
}
if (indexOfLargest != index) {
swap(arr, index, indexOfLargest);
max_heapify(indexOfLargest);
}
}
```

This operation takes *O(log n)*

Here for the index passed, we are comparing it with its child elements. If any child is greater than child, it will be swapped. Since, we have put a newer element to its kid. That sub-tree also has to satisfy max-heap property. And, we go in a natural recursive algorithm.

```
void buildMaxHeap(int[] arr, int heapsize) {
for (int i=heapsize/2; i>=0; i--) {
max_heapify(arr, i, heapsize);
}
}
```

This operation takes *O(n log n)* (including time complexity of max_heapify() as well)

In above example of input, after buildMaxHeap, it will look like:

```
473,445,295,310,404,199,257,25,21,47
473
/ \
445 295
/ \ / \
310 404 199 257
/ \ /
25 21 47
```

Heap data structure has many usage, and is very useful data structure.

- Used for implementing Priority Queue (Max/Min Priority Queue)
- Maintaining
*n*largest or smallest elements

Min Priority Queue is a data structure which manage a list of keys(values). And…

Problem Statement You are given two non-empty linked lists representing two non…

Problem Statement You are given an n x n 2D matrix representing an image, rotate…

Problem Statement There are two sorted arrays nums1 and nums2 of size m and n…

Problem Statement Determine if a 9x9 Sudoku board is valid. Only the filled…

First try to understand question. Its a binary tree, not a binary search tree…

Introduction Strapi is a backend system provides basic crud operations with…

Introduction I had to create many repositories in an Github organization. I…

Introduction I was trying to download some youtube videos for my kids. As I have…

Introduction In this post, we will explore some useful command line options for…

Introduction In this post, we will see how we can apply a patch to Python and…

Introduction We will introduce a Package Manager for Windows: . In automations…