如何实现堆排序算法？

堆排序是一种利用堆这种数据结构的排序算法。

我们可以使用数组实现一个最小堆:

public class MinHeap {
    private int[] heap;   // 堆数组
    private int size;    // 堆中元素个数

    public MinHeap(int capacity) {
        heap = new int[capacity];
        size = 0;
    }

    public void add(int ele) {
        heap[size++] = ele;
        int index = size - 1;
        while (index > 0) {
            int parent = (index - 1) / 2;
            if (heap[parent] <= ele) break;
            swap(heap, parent, index);
            index = parent;
        }
    }

    public int poll() {
        int ret = heap[0];
        heap[0] = heap[--size]; 
        int index = 0;
        while (index * 2 + 1 < size) {   // 存在子节点
            int left = index * 2 + 1;
            int right = left + 1;
            int minIndex = left;
            if (right < size && heap[right] < heap[left]) {
                minIndex = right;
            }

            if (heap[minIndex] >= heap[index]) break;
            swap(heap, minIndex, index);
            index = minIndex;
        }

        return ret;
    }

    private void swap(int[] heap, int i, int j) {
        int temp = heap[i];
        heap[i] = heap[j];
        heap[j] = temp;
    }
}

堆排序算法步骤:

1. 构建一个最小堆 MinHeap,默认容量为数组长度。
2. 把数组所有元素依次添加到堆中,每添加一个元素调用 add() 方法进行上滤操作,保证堆的最小值在根节点。
3. 调用 poll() 方法获取堆顶元素,并对剩余元素进行下滤操作,使得堆的最小值仍在根节点。
4. 重复步骤 3,直到堆变空。
5. 把所有从堆中取出的元素按顺序连接起来,即得到有序数组。

时间复杂度 O(nlogn),空间复杂度 O(1)。

所以,堆排序的关键是:

1. 构建一个最小堆,add() 方法进行上滤操作。
2. poll() 方法取出堆顶元素并下滤,保证堆的最小值在根节点。
3. 重复步骤 2 直到堆为空,得到的元素顺序便是排序结果。