Heap Sort

Introduction

Prerequisites: Heap

Heap sort is a sort that takes advantage of the efficiencies of a heap. To sort an array of N elements, we convert it to a heap by using heapify and then we pop out all the elements one by one since can the root element will be either the maximum or minimum element.

Implementation

We can simply use the heap built into the standard library for this sort by adding all the elements to the array which is O(n log n) and then popping all the elements which is O(n log n).

Code

public void heapSort(int[] arr) {
  // Use a built-in heap.
  PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

  // Add all elements into heap.
  for (int i = 0; i < arr.length; i++) {
    pq.add(arr[i]);
  }
  // Pop all elements from heap.
  for (int i = 0; i < arr.length; i++) {
    arr[i] = pq.poll();
  }
}