堆排序算法

1 堆

堆是一棵二叉树，有以下几个约束条件：

（1）用数组表示

（2）是一棵完全二叉树

所谓完全二叉树就是用数组表示的时候，孩子节点的下标和父节点的下标满足如下的关系：

left = 2 * parent + 1,

right = 2 * parent + 2，

下标从 0 开始。

下图中，左边的二叉树是完全二叉树，右边的二叉树不是完全二叉树。

（3）分大顶堆和小顶堆

如果子节点的数值都不大于父节点，那么堆是大顶堆。如果子节点的数值都不小于父节点，那么堆是小顶堆。下图中，左边是大顶堆，右边是小顶堆。

大顶堆和小顶堆与二叉搜索树的约束条件是不一样的：对于堆来说只要求子节点和父节点之间的大小关系，至于左子节点和右子节点的大小关系，没有要求；对于二叉排序树来说，要求 left < root <= right。

2 堆排序

使用堆这种数据结构可以进行排序，属于选择排序的思想。大顶堆用于从小到大排序，小顶堆用于从大到小排序。

以大顶堆为例，为什么从小到大排序使用大顶堆呢 ？如下图所示，堆排序是属于选择排序，每一次选择的时候都是选择的 root 节点(root 节点确定是堆中的最大值)，然后将选择的节点从后向前排。比如第一次选择，选择的数值是 100，要和最后一个位置进行交换。交换之后的数组，[0, 7] 位置的元素需要进行调整，把数据再调整为一个堆。如果从小到大排序使用小顶堆，那么第一次选择的就是最小值，这个值不需要动位置，那么 [1, 8] 位置的数据就需要进行调整，调整到满足堆的要求。这个时候 [1, 8] 中的数据，子节点和父节点下标不满足 left = 2 * parent + 1, right = 2 * parent + 2，无法操作。所以从小到大排序使用大顶堆，从大到小排序使用小顶堆。

使用堆排序一般分为两步：

（1）创建初始堆

（2）选择排序

选择排序的每一步又分两步，选择和调整。每选择一个数放到指定位置之后都要对堆进行调整，使数据满足堆的要求。

leetcode 中有一个数组排序题，可以使用堆排序。

. - 力扣（LeetCode）

class Solution {
public:
    // 昨天写的，今天再写，还是会出错
    vector<int> sortArray(vector<int>& nums) {
      heapSort(nums);
      return nums;  
    }
    
    // 堆排序算法
    void heapSort(vector<int> &nums) {
        // 创建初始堆
        createHeap(nums);
        int size = nums.size();

        // 选择排序过程
        for (int i = 0; i < size; i++) {
            // 选择和交换
            int tmp = nums[0];
            nums[0] = nums[size - 1 - i];
            nums[size - 1 - i] = tmp;
            // 调整堆
            // 随着排序的进行，确定好位置的数据越来越多
            // 堆排序的时候需要关心的数据个数也在递减
            adjustHeap(nums, 0, size - 1 - i - 1);
        }
    }
    
    // 创建初始堆
    void createHeap(vector<int>& nums) {
        int size = nums.size();
        // 堆是一棵二叉树
        // 创建堆的时候，从二叉树的倒数第二层往上遍历
        // 每个节点都要进行判断，如果需要调整，则进行调整
        int start = size / 2;
        for (int i = start; i >= 0; i--) {
            adjustHeap(nums, i, size - 1);
        }
    }
    
    // 调整堆
    // 创建初始堆和调整堆，都会使用这个函数
    // 选择过程调整堆的时候，因为就改变了 root 这一个位置
    // 除了 root 之外，其它节点都满足堆的要求
    // 所以从 root 节点开始，调整一次堆就可以了，调整之后就满足堆的要求了
    void adjustHeap(vector<int>& nums, int start_index, int end_index) {
      if (start_index >= end_index) {
          return;
      }
      
      // 在 parent，left child, right child 中选择一个较大的值
      int bigger_index = start_index;
      int left_child_index = 2 * start_index + 1;
      int right_child_index = left_child_index + 1;
      if (left_child_index <= end_index && nums[left_child_index] > nums[bigger_index]) {
          bigger_index = left_child_index;
      }

      if (right_child_index <= end_index && nums[right_child_index] > nums[bigger_index]) {
          bigger_index = right_child_index;
      }
      
      // 如果 left child 和 right child 的值都不大于 parent
      // 那么不需要交换，这一层不需要交换
      // 那么下边的也是满足要求的，所以调整结束，可以直接返回了
      // 如果这次需要交换，那么就进行交换，然后递归向下遍历
      if (bigger_index != start_index) {
          int tmp = nums[start_index];
          nums[start_index] = nums[bigger_index];
          nums[bigger_index] = tmp;
          adjustHeap(nums, bigger_index, end_index);
      }
    }
};

原文地址：https://blog.csdn.net/weixin_38184628/article/details/138002513

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！