堆排序

[sshwy]

https://oi-wiki.org/basic/heap-sort/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[XOIERX]

GOOD

[Kreedy-Ke]

是否可以加上 C++ <queue> 库中的 priority_queue 数据类型，这也是基于堆的，且比赛中也可以使用

[Cephascqs]

可以，毕竟它可以帮你排序

[zhangjialin996]

class Solution {
  public int[] sortArray(int[] nums){
    heapSort(nums);
    return nums;
  }

  public void heapSort(int[] nums){
      int len = nums.length;
      // 建堆
      for(int i = (len - 2) / 2; i >= 0; i--) {
          heapify(nums, i, len - 1);
      }
      for(int i = len - 1; i > 0; i--) {
          swap(nums, i, 0);
          heapify(nums, 0, i - 1);
      }
  }


  // 大顶堆 : 调整某个结点使得整个子树满足大顶堆要求
  public void heapify(int[] nums, int root, int end){
      int p = root;
      int c = root * 2 + 1; // 左孩子
      while(c <= end){
          if(c + 1 <= end && nums[c] <= nums[c + 1]) c++;
          if(nums[p] >= nums[c]) return ;
          else {
              swap(nums, p, c);
              p = c;
              c = p * 2 + 1;
          }
      }        
  }

  public void swap(int[] nums, int i, int j){
      int tmp = nums[i];
      tmp = nums[i];
      nums[i] = nums[j];
      nums[j] = tmp;
  }
}

关于下标和边界条件的快速选择方法：画一棵树模拟一下

[zhangjialin996]

java底层PriorityQueue中使用了二叉堆，默认小顶堆，基于此`heapify还有一种写法：
java源码

  public void heapify(int[] nums, int root, int end){
      int p = root;
      int c = root * 2 + 1; // 左孩子
      int curRootValue = nums[root];
      while(c <= end){
          if(c + 1 <= end && nums[c] <= nums[c + 1]) c++;
          if(curRootValue >= nums[c]) break ;
          else {
              // swap(nums, p, c);
              nums[p] = nums[c];
              p = c;
              c = (p << 1) + 1;
          }
      }        
      nums[p] = curRootValue;
  }

其实就是把当前需要调整的堆的堆顶元素取出来，如果孩子优先级更高，那就用孩子覆盖当前堆顶。最终可以找到一个合适位置填充，而不是每次都进行交换。

[Skys0]

感觉C++代码第四行写错了，左儿子应该是 2*i

[ATION001]

可能是写法不一样吧。