### Min Priority Queue Implementation with Heap Data structure

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

May 11, 2019

Its a kind of incremental insertion technique, where the algorithm build up sorting by first sorting n-1 items.

Or, we can say that we pick an element on n-1 items, and insert in a position where all items on the left side are less than or equal to this number.

The algorithm works in two loops, where outer most loop iterate over complete array. To be more precise, We iterate from index-1 to end of array. Leaving index-0 to be used by inner loop.

In inner loop, the loop variable takes the index from outer loop index variable. It takes a backup of the value present on that index, and go backward toward 0-index. It shift previous elements to next position unless they are greater than the value for which we have taken backup.

In short, inner loop tries to sort the n-1 part of array by shifting any bigger element to right. And, **insert** the element to the final position.

See the code here:

```
public void sort(int[] arr) {
int len = arr.length;
for (int i=1; i<len; i++) {
int key = arr[i];
int j = i-1;
while (j >= 0 && key < arr[j]) {
arr[j+1] = arr[j];
j--;
}
arr[j+1] = key;
}
}
```

- It does not use extra memory. And, is in-place algorithm.
- Its stable, as it does not change order of same value elements.
- It is more efficient in practice than Bubble Sort and Selection Sort
- It is well suited for small data sets.

The algorithm runs on O(n^2) in worst case.

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

Problem Statement Given a signed integer, reverse digits of an integer. Return…

This topic is one of the most common studied. When somebody started preparation…

Problem Statement Write a function that reverses a string. The input string is…

Counting sort runs on relatively smaller set of input. Counting sort calculates…

This is kind of preliminary technique of sorting. And, this is the first…

Problem Statement You are given a string text of words that are placed among…

Problem Statement You are given a rows x cols matrix grid. Initially, you are…

Problem Statement Given a string s, return the maximum number of unique…

Problem The Leetcode file system keeps a log each time some user performs a…

Problem Statement Replace all spaces in a string with ‘%20’ (three characters…

Problem Implement an algorithm to determine if a string has all the characters…