C++中二叉堆排序详解

什么是二叉堆排序

二叉堆是一种特殊的二叉树，它有两个特性：

1. 根节点的键值是所有节点中最小/最大的；
2. 对于节点i的键值一定不大/小于它的父节点i/2。

根据第二个规则，我们可以对于任何一个节点i，以i为根的子树都是一个小根堆/大根堆。将二叉堆中最小/最大的根节点取出，然后将最后一个节点放到根位置，再对根节点进行一次向下调整的操作，就可以将次小/大的节点取出。以此类推，不断重复这个过程，直到所有的节点都取出来了，则排序完成。

C++实现

向下调整

向下调整的过程需要通过一个函数来实现，如果当前节点的子节点比当前节点更小（小根堆）或更大（大根堆），则需要对当前节点进行调整，将当前节点与子节点交换。

void adjustDown(vector<int>& nums, int i, int len) {
    int temp = nums[i];
    int targetIndex = i * 2 + 1;
    while (targetIndex < len) {
        if (targetIndex + 1 < len and nums[targetIndex+1] < nums[targetIndex]) {
            targetIndex ++;
        }
        if (nums[targetIndex] >= temp) {
            break;
        }
        nums[i] = nums[targetIndex];
        i = targetIndex;
        targetIndex = 2 * i + 1;
    }
    nums[i] = temp;
}

建立二叉堆

建立二叉堆其实就是将一个乱序的数组转化为二叉堆。我们可以在数组中依次取出每个数字，将其插入到构建好的二叉堆中。

void buildHeap(vector<int>& nums) {
    int len = nums.size();
    int endNode = len / 2 - 1;
    for (int i = endNode; i >= 0; i--) {
        adjustDown(nums, i, len);
    }
}

排序

当我们建立好一颗二叉堆时，有一个非常重要的性质就是：最小/大值一定在数组的第一个位置，我们可以将其直接取出并放在排序好后数组的最后。通过这个方式，我们不断取出最小/大值，一次放在排序后的数组中，直到整个数组都排序完成。

void heapSort(vector<int>& nums) {
    // 建立二叉堆
    buildHeap(nums);

    // 从最后一个节点开始往前取数
    int len = nums.size();
    for (int i = len - 1; i > 0; i--) {
        swap(nums[0], nums[i]);  // 将最后一个元素放在排序好的队列首部
        adjustDown(nums, 0, i);  // 建立一个新的二叉堆，并将下一个最小/大值放在根节点位置
    }
}

示例

以小根堆为例，对于一个乱序的数组 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]，我们可以通过以下方式进行二叉堆排序：

vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};

// 将乱序数组转化为小根堆
buildHeap(nums);
// 输出建立完成的小根堆
cout << "Heap: ";
for (int num: nums) {
    cout << num << " ";
}
cout << endl;

// 对小根堆进行排序
heapSort(nums);
// 输出排序完成后的数组
cout << "Sorted nums: ";
for (int num: nums) {
    cout << num << " ";
}

输出结果如下：

Heap: 1 1 2 3 3 4 9 6 5 5 5 
Sorted nums: 1 1 2 3 3 4 5 5 5 6 9 

总结

通过现在的学习，我们了解了什么是二叉堆排序，也实现了在C++中二叉堆排序的过程。二叉堆排序是常用的排序算法，其时间复杂度为O(nlogn)。