List of Sorting Algorithms
This topic is one of the most common studied. When somebody started preparation…
July 03, 2019
This is another very useful sorting algorithm based on Heap data structure. Read more about Heap Data Structure
In this algorithn, we first prepare heap which satisfies max-heap property. Once we get out max heap ready. We get maximum element at the top. We swap this element with the last index element. And, reduce heapsize by one. Now, since we have put a newer element on top. We will just run max_heapify() algorithm on this array with new heapsize.
Finally we get the sorted array.
In a loop starting from last index
See the code here:
public class HeapSort {
private int[] arr;
private int heapsize;
public HeapSort(int[] arr) {
this.arr = arr;
this.heapsize = this.arr.length;
}
private int getLeftChild(int index) {
return (index * 2) + 1;
}
private int getRightChild(int index) {
return (index * 2) + 2;
}
private void max_heapify(int index) {
int l = this.getLeftChild(index);
int r = this.getRightChild(index);
int indexOfLargest = index;
if (l < this.heapsize && this.arr[l] > this.arr[index]) {
indexOfLargest = l;
}
if (r < this.heapsize && this.arr[r] > this.arr[indexOfLargest]) {
indexOfLargest = r;
}
if (indexOfLargest != index) {
ArrayUtils.swap(this.arr, index, indexOfLargest);
this.max_heapify(indexOfLargest);
}
}
private void buildMaxHeap() {
for (int i=this.heapsize/2; i>=0; i--) {
this.max_heapify(i);
}
}
public void doHeapSort() {
this.buildMaxHeap();
int l = this.arr.length;
for (int i=l-1; i>0; i--){
ArrayUtils.swap(this.arr, 0, i);
this.heapsize--;
this.max_heapify(0);
}
}
}
The algorithm runs on O(n log n) in worst/average case.
This topic is one of the most common studied. When somebody started preparation…
Problem Statement You are given a rows x cols matrix grid. Initially, you are…
Problem Statement Write a function that reverses a string. The input string is…
Max Priority Queue is a data structure which manage a list of keys(values). And…
First try to understand question. Its a binary tree, not a binary search tree…
Problem Statement Given a string, find the length of the longest substring…
In this post, we will see some of the frequently used concepts/vocabulary in…
System design interview is pretty common these days, specially if you are having…
Introduction You are given an array of integers with size N, and a number K…
Graph Topological Sorting This is a well known problem in graph world…
Problem Statement Given a Binary tree, print out nodes in level order traversal…
Problem Statement Given an array nums of n integers and an integer target, are…