Heap Sort

Wikipedia has very good explanation about heap sort and why its time complexity is O(nlogn):

“The heapsort algorithm involves preparing the list by first turning it into a max heap. The algorithm then repeatedly swaps the first value of the list with the last value, decreasing the range of values considered in the heap operation by one, and sifting the new first value into its position in the heap. This repeats until the range of considered values is one value in length.

The steps are:

  • Call the buildMaxHeap() function on the list. Also referred to as heapify(), this builds a heap from a list in O(n) operations.
  • Swap the first element of the list with the final element. Decrease the considered range of the list by one.
  • Call the siftDown() function on the list to sift the new first element to its appropriate index in the heap.
  • Go to step (2) unless the considered range of the list is one element.

The buildMaxHeap() operation is run once, and is O(n) in performance. The siftDown() function is O(log(n)), and is called n times. Therefore, the performance of this algorithm is O(n + n * log(n)) which evaluates to O(n log n).”


Some key points to understand this algorithm and its implementation:

  • the heap data structure is actually a virtual thought, it exists only in our imagination, in reality, we’re only re-positioning the elements into different indices, this is also why heap sort space complexity is O(1), since it doesn’t require any extra memory
  • how do we construct this virtual heap data structure? some keys to understand it:
    • regard the array as an level order traversal of a complete binary tree (draw out the picture, and then you’ll have a better understanding)
    • how to construct a max heap? we always want the parent’s val to be greater than its both children’s val, so we swap the two if we find a situation that doesn’t follow this rule and recursively do it.
    • how do we find a node’s left and right children?
      • if you draw out the tree, you’ll figure out that: a node with index i, its left child will be 2*i and its right child will be 2*i+1, if the two children exist.


  • Heap sort in NOT stable: the relative order of equal elements might be changed since heapsort peeks the largest element and put it at the last of list.

Used the wikipedia example input: 6, 5, 3, 1, 8, 7, 2, 4 to test my code:heap_sort

public class _20160710_HeapSortAgain {
private static int N;
public static void sort(int[] nums){
for(int i = N; i > 0; i--){//i doesn't need to be equal to zero, because we don't need to swap zero-indexed number with itself
swap(nums, i, 0);//we always swap the first element in the array which means it's at the root of the heap with the number at index i which is the largest index in the UN-sorted array
N -= 1;//don't remember to decrement N by 1, because we only need to worry about one number fewer each time
maxheap(nums, 0);//then we always update the heap for the number at index zero
private static void heapify(int[] nums) {
N = nums.length-1;
for(int i = N/2; i >= 0; i--){//here we need i to be equal to zero because we need to do maxheap() on its first element as well
maxheap(nums, i);
private static void maxheap(int[] nums, int i) {
int leftChildIndex = 2*i;
int rightChildIndex = leftChildIndex+1;
int max = i;
if(leftChildIndex <= N && nums[leftChildIndex] > nums[i]){
max = leftChildIndex;
if(rightChildIndex <= N && nums[rightChildIndex] > nums[max]){
max = rightChildIndex;
if(i != max){
swap(nums, i, max);
maxheap(nums, max);
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
public static void main(String...strings){
int[] nums = new int[]{6,5,3,1,8,7,2,4};
// int[] nums = new int[]{1,2,3,4,5,6};
// int[] nums = new int[]{6,5,4,3,2,1};
print("BEFORE printing, nums are: ", nums);
print("AFTER printing, nums are: ", nums);
private static void print(String msg, int[] nums) {
for(int i : nums){
System.out.print(i + ", ");


Garbage Collection

  • GC is a mechanism provided by JVM to reclaim heap space from objects
  • When does an object become eligible for garbage collection?
    • If it’s not reachable by any live threads or any static references, or you could say, when all of its references become null.
    • Cyclic dependencies do not count which means that it’s also eligible for GC. e.g. Object A has reference to Object B and Object B also references Object A, and they don’t have any live thread references, then both Object A and B are eligible for GC.
  • This is a pretty handy and quick description about how GC works in Java: http://www.dynatrace.com/en/javabook/how-garbage-collection-works.html


QuickSort doesn’t require extra space, average time is O(nlgn).


  1. Pick a pivot and sort all elements in the array that are smaller than the pivot to the left of the chosen pivot, and all that are bigger than the pivot to the right of it
  2. recursively sort two sublists
  3. Note: the pivot could be chosen in multiple ways:
    1. you can pick first element in the array
    2. you can pick last element in the array
    3. you can pick median element in the array
    4. you can pick random element in the array
  4. The pivot you pick could result in completely different sorting efficiency under extreme cases: http://stackoverflow.com/questions/2415193/worst-case-for-quicksort-when-can-it-occur

The following partition() method takes the last element as the pivot. In its partition() method: it sets the last element as the pivot, then it keeps an index i = low-1, then use another index j to loop through all elements from low to high-1, when we find any element nums[j] that is smaller than or equal to pivot (i.e. nums[high]), we increment i by 1 first, then we swap nums[j] with nums[i], notice, we swap nums[j] with nums[i], not with nums[high] or anything else, we swap nums[high] after we finish iterating through low to high-1, this is to do this: place all elements that are smaller than the pivot to the left of the pivot, after iterating through from low to high-1, we swap nums[i+1] with nums[high], this is to place nums[high] (i.e. current pivot) to the correct position, then we return i+1 as the pivot as all elements from low to i are sorted already.

I put my partition() function into this site and it’s accepted: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

int[] quickSort_20160628(int[] nums){
quickSort_20160628(nums, 0, nums.length-1);
return nums;

void quickSort_20160628(int[] nums, int low, int high) {
if(low < high){
int pi = partition_20160628(nums, low, high);
quickSort_20160628(nums, low, pi-1);
quickSort_20160628(nums, pi+1, high);

int partition_20160628(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low-1;
for(int j = low; j <= high-1; j++){
if(nums[j] <= pivot){

int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;

int temp = nums[i+1];
nums[i+1] = nums[high];
nums[high] = temp;
return i+1;

Then, just out of curiosity, I followed the same pattern, implemented the partition() function by picking the first element as the pivot, similar idea in the partition() function: similar to the partition() function in choosing last as pivot where it uses a for loop to find all elements that are smaller than pivot to place them to the left most possible, this partition_pivot_first_20160628I() function uses a for loop to find all elements that are bigger than the chosen pivot and places them to the right most possible.

Cool! I figured this partition method myself by completely understanding it first. Praise the Lord!

Also, don’t forget to put if(low < high){} at the main function!!! Otherwise, it won’t work!

It’s also accepted here: http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

int[] quickSort_pivot_first_20160628(int[] nums){
quickSort_pivot_first_20160628(nums, 0, nums.length-1);
return nums;

private void quickSort_pivot_first_20160628(int[] nums, int low, int high) {
if (low < high) {
int pi = partition_pivot_first_20160628(nums, low, high);
quickSort_pivot_first_20160628(nums, low, pi - 1);
quickSort_pivot_first_20160628(nums, pi + 1, high);

private int partition_pivot_first_20160628(int[] nums, int low, int high) {
int pivot = nums[low];
int i = high+1;
for(int j = high; j > low; j--){
if(nums[j] > pivot){

int temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;

int temp = nums[low];
nums[low] = nums[i-1];
nums[i-1] = temp;

return i-1;


Implement quickSort() that takes median element as the pivot, it’s a bit different from the previous two, just in the way it’s written: it doesn’t use one more help function: partition(), instead, it uses just one function which does both recursion and partition. The fundamental idea behind the three is definitely the same: keep picking one element as pivot, keep placing all elements in the array that are smaller than the pivot to the left of the pivot and those that are bigger to the right.

int[] quickSort_pivot_median_20160628(int[] nums){
quickSort_pivot_median_20160628(nums, 0, nums.length-1);
return nums;

void quickSort_pivot_median_20160628(int[] nums, int low, int high) {
if(nums == null || nums.length == 0) return ;
if(low >= high) return;

int i = low, j = high, mid = (low+high)/2, pivot = nums[mid];

while(i <= j){
while(nums[i] < pivot) i++;
while(nums[j] > pivot) j--;
if(i <= j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;

if(low < j) quickSort_pivot_median_20160628(nums, low, j);
if(i < high) quickSort_pivot_median_20160628(nums, i, high);