简介

堆参考
优先队列(堆)
堆排序步骤：

  1. 首先将数组nums构建成一个大(或小)顶堆
  2. 将堆顶元素nums[0]与堆最后一个未排序元素nums[end]交换
  3. 此时堆顶元素nums[0]可能不是最大值，重新调整堆 nums[0] .. nums[end-1]
  4. 重复2,3步知道整个数组有序

    效率

  • 时间复杂度：堆排序 - 图1
  • 空间复杂度：堆排序 - 图2

  • 稳定性：不稳定

    实现

    ```rust pub fn heap_sort(mut nums: Vec) -> Vec { // 从最后一个非叶子节点开始，从右到左，从上到下构建堆 let length = nums.len(); for i in (0..=nums.len() / 2 - 1).rev() {

    1.   Self::adjust_heap(&mut nums, i, length);

    }

    for j in (1..nums.len()).rev() {

      // 堆顶元素与最后一个节点交换
  nums.swap(0, j);
  // 交换后，调整堆
  Self::adjust_heap(&mut nums, 0, j);

    }

    nums }

/// 调整堆，将堆顶元素调整到合适位置 fn adjust_heap(nums: &mut [i32], mut index: usize, heap_size: usize) { // 调整的元素 let adj_val = nums[index]; // 左子节点 let mut k = index * 2 + 1; while k < heap_size { // 如果左子节点小于右子节点，选择右子节点 if k + 1 < heap_size && nums[k] < nums[k + 1] { k = k + 1; }

    // 如果子节点大于父节点，交换(即子节点上移)，记录新的位置
    if nums[k] > adj_val {
        nums.swap(k, index);
        index = k;
    }

    // 继续循环左子节点
    k = 2 * k + 1;
}

nums[index] = adj_val;

} ```