Basic Heap Sort

I. Concept and Introduction

Heap sort is a sorting algorithm designed using the heap data structure.

A heap is a structure similar to a complete binary tree that also satisfies the heap property: the key or index of a child node is always less than (or greater than) its parent node.

II. Applicability

Previously, the process of constructing a heap involved inserting each data element one by one using the insert method and shift up, resulting in a time complexity of O(nlogn). This section introduces a heap construction process called Heapify, which has a time complexity of O(n).

III. Process Illustration

A complete binary tree has an important property: the index of the first non-leaf node is n/2, where n is the number of elements (assuming array indexing starts from 1).

Index 5 is the first non-leaf node. We start from this node and move forward, performing shift down operations on each element as the root node to satisfy the max-heap property.

After performing shift down on index 5, 22 and 62 swap positions.

Perform shift down on the element at index 4.

Perform shift down on the element at index 3.

Perform shift down on the element at index 2.

Finally, perform shift down on the root node, completing the heap sort process.

IV. Java Example Code

Source Code Download: Download

src/tutorialpro/heap/Heapify.java File Code:

package tutorialpro.heap;

import tutorialpro.sort.SortTestHelper;

/**
 * Heap sort using heapify
 */
public class Heapify<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Constructor, create a max heap from a given array
    // The construction process has a time complexity of O(n)
    public Heapify(T arr[]){

        int n = arr.length;

        data = (T[])new Comparable[n+1];
        capacity = n;

        for( int i = 0 ; i < n ; i ++ )
            data[i+1] = arr[i];
        count = n;
        // Start from the first non-leaf node
        for( int i = count/2 ; i >= 1 ; i -- )
            shiftDown(i);
    }
    // Return the number of elements in the heap
    public int size(){
        return count;
    }
    // Return a boolean indicating whether the heap is empty
    public boolean isEmpty(){
        return count == 0;
    }
    // Insert a new element into the max heap
    public void insert(T item){
        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // Extract the top element from the max heap, which is the largest data stored
    public T extractMax(){
        assert count > 0;
        T ret = data[1];
        swap( 1 , count );
        count --;
        shiftDown(1);
        return ret;
    }
    // Get the top element of the max heap
    public T getMax(){
        assert( count > 0 );
        return data[1];
    }

    // Swap two elements in the heap with indices i and j
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

//********************
//* Max Heap Core Helper Function
//********************
private void shiftUp(int k) {
    while (k > 1 && data[k/2].compareTo(data[k]) < 0) {
        swap(k, k/2);
        k /= 2;
    }
}

private void shiftDown(int k) {
    while (2*k <= count) {
        int j = 2*k; // In this loop, data[k] and data[j] swap positions
        if (j+1 <= count && data[j+1].compareTo(data[j]) > 0)
            j++;
        // data[j] is the maximum value between data[2*k] and data[2*k+1]

        if (data[k].compareTo(data[j]) >= 0) break;
        swap(k, j);
        k = j;
    }
}

// Test heapify
public static void main(String[] args) {
    int N = 100;
    Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
    Heapify<Integer> heapify = new Heapify<Integer>(arr);
    // Gradually extract data from heapify using extractMax
    // The order of extraction should be in descending order
    for (int i = 0; i < N; i++) {
        arr[i] = heapify.extractMax();
        System.out.print(arr[i] + " ");
    }

    // Ensure that the arr array is sorted in descending order
    for (int i = 1; i < N; i++)
        assert arr[i-1] >= arr[i];
}