YouTipHeap Sort
## Basic Heap Sort
### I. Concept and Introduction
Heap sort (Heapsort) is a sorting algorithm designed using the heap data structure.
A heap is an approximately complete binary tree structure that also satisfies the heap property: the key values or indices of child nodes are always less than (or greater than) those of their parent node.
### II. Applicability
The process of constructing a heap we previously discussed involved calling the `insert` method one data point at a time, using `shift up` to insert each element into the heap. The time complexity of this algorithm is O(nlogn). This section introduces a process for constructing a heap for sorting, called **Heapify**, with an algorithm 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 obtained by taking the integer value of **n/2**, where **n** is the number of elements (assuming array indexing starts from 1).
!(#)
The element at index 5 is the first non-leaf node. We start from it and move backward, performing a `shift down` operation on each element as the root node to satisfy the max-heap property.
After performing the `shift down` operation on the element at 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, and the entire heap sort process is complete.
!(#)
### IV. Java Example Code
**Source code package download:*## src//heap/Heapify.java File Code:
```java
package .heap;
import .sort.SortTestHelper;
/**
* Heap sort using heapify
*/
public class Heapify{
protected T[] data;
protected int count;
protected int capacity;
// Constructor, creates a max heap from a given array
// The time complexity of this heap construction process is O(n)
public Heapify(T arr[]){
int n = arr.length;
data =(T[])new Comparable[n+1];
capacity = n;
for(int i =0; i =1; i --)
shiftDown(i);
}
// Returns the number of elements in the heap
public int size(){
return count;
}
// Returns a boolean indicating whether the heap is empty
public boolean isEmpty(){
return count ==0;
}
// Inserts a new element 'item' into the max heap
public void insert(T item){
assert count +10;
T ret = data;
swap(1 , count );
count --;
shiftDown(1);
return ret;
}
// Gets the top element of the max heap
public T getMax(){
assert( count >0);
return data;
}
// Swaps two elements in the heap with indices i and j
private void swap(int i, int j){
T t = data;
data= data;
data= t;
}
//********************
//* Core helper functions for max heap
//********************
private void shiftUp(int k){
while( k >1&& data[k/2].compareTo(data)<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 and data will swap positions
if( j+10)
j ++;
// data is the maximum of data[2*k] and data[2*k+1]
if( data.compareTo(data)>=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 heapify =new Heapify(arr);
// Gradually extract data from heapify using extractMax
// The order of extraction should be from largest to smallest
for(int i =0; i < N ; i ++){
arr= heapify.extractMax();
System.out.print(arr+" ");
}
// Ensure the arr array is sorted from largest to smallest
for(int i =1; i = arr;
}
}