Basic Heap Sort
1. Concept and Introduction
Heapsort is a sorting algorithm designed using the heap data structure.
A heap is a structure that approximates a complete binary tree and simultaneously satisfies the heap property: that is, the key or index of a child node is always less than (or greater than) its parent node.
II. Application Instructions
Our previous process of building a heap was to insert data one by one into the heap by calling the insert method using shift up; the time complexity of this algorithm isO(nlogn), the process of constructing a heap sort introduced in this section is calledHeapify, the algorithm time complexity isO(n)。
III. Process Diagram
A complete binary tree has an important property: the index of the first non-leaf node isn/2the index value obtained by taking an integer, wherenis the number of elements (assuming array indices start from 1).
The position at index 5 is the first non-leaf node. Starting from it, we move forward one by one, performing the shift down operation on each element as the root node to satisfy the max heap property.
After the shift down operation at index 5, 22 and 62 swap positions.
Perform the shift down operation on the element at index 4.
Perform the shift down operation on the element at index 3.
Perform the shift down operation on the element at index 2.
Finally, perform the shift down operation on the root node, and the entire heapsort process is complete.
IV. Java Example Code
Source Code Package Download:Download
src/example/heap/Heapify.java file code:
import example.sort.SortTestHelper;
/**
* Use heapify to perform heap sort
*/
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 heap construction process has time complexity 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 element that is not a 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 item 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, i.e., the largest data stored in the heap
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 the two elements at indices i and j in the heap
private void swap(int i, int j){
T t = data[i];
data[i] = data[j];
data[j] = t;
}
//********************
//* Max heap core helper functions
//********************
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 iteration, data[k] and data[j] swap positions
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] is the maximum of 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 the data in heapify using extractMax
// The extraction order should be from largest to smallest
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapify.extractMax();
System.out.print(arr[i] + " ");
}
// Ensure the arr array is sorted from largest to smallest
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}