妙用二叉树后序位置：归并排序

// 直接利用优先级队列对数组从小到大排序
func sort(nums []int) {
    // 创建一个从小到大排序元素的小顶堆
    pq := NewSimpleMinPQ(len(nums))

    // 先把所有元素插入到优先级队列中
    for _, num := range nums {
        // push 操作会自动构建二叉堆，时间复杂度为 O(logN)
        pq.Push(num)
    }

    // 再把所有元素取出来，就是从小到大排序的结果
    for i := 0; i < len(nums); i++ {
        // pop 操作从堆顶弹出二叉堆堆中最小的元素，时间复杂度为 O(logN)
        nums[i] = pq.Pop()
    }
}

堆排序的两个关键步骤

1、原地建堆（Heapify）：直接把待排序数组原地变成一个二叉堆。

2、排序（Sort）：将元素不断地从堆中取出，最终得到有序的结果。

// 小顶堆的上浮操作，时间复杂度是树高 O(logN)
func minHeapSwim(heap []int, node int) {
    for node > 0 && heap[parent(node)] > heap[node] {
        swap(heap, parent(node), node)
        node = parent(node)
    }
}

// 小顶堆的下沉操作，时间复杂度是树高 O(logN)
func minHeapSink(heap []int, node, size int) {
    for left(node) < size || right(node) < size {
        // 比较自己和左右子节点，看看谁最小
        min := node
        if left(node) < size && heap[left(node)] < heap[min] {
            min = left(node)
        }
        if right(node) < size && heap[right(node)] < heap[min] {
            min = right(node)
        }
        if min == node {
            break
        }
        // 如果左右子节点中有比自己小的，就交换
        swap(heap, node, min)
        node = min
    }
}

// 大顶堆的上浮操作
func maxHeapSwim(heap []int, node int) {
    for node > 0 && heap[parent(node)] < heap[node] {
        swap(heap, parent(node), node)
        node = parent(node)
    }
}

// 大顶堆的下沉操作
func maxHeapSink(heap []int, node, size int) {
    for left(node) < size || right(node) < size {
        // 小顶堆和大顶堆的唯一区别就在这里，比较逻辑相反
        // 比较自己和左右子节点，看看谁最大
        max := node
        if left(node) < size && heap[left(node)] > heap[max] {
            max = left(node)
        }
        if right(node) < size && heap[right(node)] > heap[max] {
            max = right(node)
        }
        if max == node {
            break
        }
        swap(heap, node, max)
        node = max
    }
}

// 父节点的索引
func parent(node int) int {
    return (node - 1) / 2
}

// 左子节点的索引
func left(node int) int {
    return node*2 + 1
}

// 右子节点的索引
func right(node int) int {
    return node*2 + 2
}

// 交换数组中两个元素的位置
func swap(heap []int, i, j int) {
    heap[i], heap[j] = heap[j], heap[i]
}

// 将输入的数组元素从小到大排序
func sort(nums []int) {
    // 第一步，原地建堆，注意这里创建的是大顶堆
    // 只要从左往右对每个元素调用 swim 方法，就可以原地建堆
    for i := 0; i < len(nums); i++ {
        maxHeapSwim(nums, i)
    }

    // 第二步，排序
    // 现在整个数组已经是一个大顶了，直接模拟删除堆顶元素的过程即可
    heapSize := len(nums)
    for heapSize > 0 {
        // 从堆顶删除元素，放到堆的后面
        swap(nums, 0, heapSize-1)
        heapSize--
        // 恢复堆的性质
        maxHeapSink(nums, 0, heapSize)
        // 现在 nums[0..heapSize) 是一个大顶堆，nums[heapSize..) 是有序元素
    }
}

类比优先级队列的操作
这个实现思路相当于完全模拟了优先级队列的 push, pop 操作，类似下面的逻辑：

```java
void sort(int[] nums) {
    // 第一步，创建大顶堆
    SimpleMaxPQ pq = new SimpleMaxPQ();
    for (int num : nums) {
        pq.push(num);
    }

    // 第二步，排序
    int heapSize = pq.size();
    while (heapSize > 0) {
        // 因为这是大顶堆，所以 pop 出来的元素是从大到小的
        nums[heapSize - 1] = pq.pop();
        heapSize--;
    }
    // 最终 nums 数组就是从小到大排序的结果
}
```

如果还是不理解，建议回去复习一下优先级队列的实现。

// 将输入的数组元素从小到大排序
func sort(nums []int) {
    // 第一步，原地建堆，注意这里创建的是大顶堆
    // 从最后一个非叶子节点开始，依次下沉，合并二叉堆
    n := len(nums)
    for i := n / 2 - 1; i >= 0; i-- {
        maxHeapSink(nums, i, n)
    }

    // 合并完成，现在整个数组已经是一个大顶堆

    // 第二步，排序，和刚才的代码一样
    heapSize := n
    for heapSize > 0 {
        // 从堆顶删除元素，放到堆的后面
        swap(nums, 0, heapSize-1)
        heapSize--
        // 恢复堆的性质
        maxHeapSink(nums, 0, heapSize)
        // 现在 nums[0..heapSize) 是一个大顶堆，nums[heapSize..) 是有序元素
    }
}