Binary Tree Data Structure
A Binary tree is a data structure which has two children nodes attached to it…
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.
A Binary tree is a data structure which has two children nodes attached to it…
Problem Statement Given a non-empty array of digits representing a non-negative…
Problem Statement You are given two non-empty linked lists representing two non…
A Binary Search tree (BST) is a data structure which has two children nodes…
Problem Statement Given an array of integers, find if the array contains any…
Problem Implement an algorithm to determine if a string has all the characters…
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…