/**
 * ## 堆介绍
 * 堆排序是利用堆数据结构来实现的排序，堆是一颗完全二叉树的结构，但是排序的时候我们并不会
 * 真正的生成一颗二叉树，而是用数组的下标来模拟其对应的位置，由于完全二叉树的特点，任意一颗
 * 子节点都可以找到其对应的父节点，所有，我们可以用这个方式来实现节点的交换操作，如下：
 * 假设我们有一个数组[4,6,5,3,1,8,1,1] 第一个元素4对应的节下标为0,而其左子节点对应的下标
 * 就是0*2+1为1，对应元素6，右子节点的下标则是0*2+2为2对应元素5，则元素6对应的下标为1其左
 * 节点为1*2+1为3对应元素3，右叶子节点为1*2+2对应元素1，以此类推到元素3时其左节点为3*2+1为7
 * 对应元素为最后一个1，当我们计算右节点时会发现这个时候已经超过数组的最大下标，所以这个节点是不
 * 存在的，并且这个元素3对应最后一个非叶子节点
 *
 * ## 大顶堆和小顶堆
 * 在完全二叉树的基础上我们可以通过一些转换操作使每一个节点都大于其子节点，那么我们就称之为大顶堆
 * 反之，当每一个节点都小于子节点时，我们称之为小顶堆
 *
 * ## 堆排序思路
 * 当我们把一个数组以堆的方式排列好之后，再对其通过交换等操作变换为大顶堆，这个时候，arr[0]对应
 * 的元素为最大的，这个时候我们 awap(arr[0],arr[n-1]),此时数组最后一个元素就是最大的，这个时候
 * 只需要排除最后一个元素再对之前的所有元素通过交换等操作变成大顶堆，再交换最后一个元素，此时为ｎ－2,
 * 知道只剩下最后一个元素，这个时候数组就有序了
 *
 */

import { swap } from "../util/index.mjs";

/**
 * @description 自上而下的构建堆
 * @param {number[]} arr - 需要变成堆结构的数组
 */
function insertHeap(arr) {
  let n = arr.length;
  for (let i = 1; i < n; i++) {
    let cur = i;
    let parent = (i - 1) >> 1;
    while (cur >= 1 && arr[parent] < arr[cur]) {
      swap(arr, parent, cur);
      cur = parent;
      parent = (cur - 1) >> 1;
    }
  }
}

/**
 * @description 交换首尾元素之后纠正堆
 * @param {number[]} arr - 需要纠正的堆
 * @param {number} cur - 从此位置开始纠正
 * @param {number} end - 堆的结束下标
 * @returns 
 */
function correctHeap(arr, cur, end) {
  while (cur * 2 + 1 <= end) {
    // 至少有一个左孩子
    let left = cur * 2 + 1;
    let right = cur * 2 + 2;
    let max;
    if (right <= end && arr[left] < arr[right]) {
      max = right;
    } else {
      max = left;
    }
    if (arr[cur] >= arr[max]) return;
    swap(arr, cur, max);
    cur = max;
  }
}

/**
 * @description 自上而下的堆排序
 * @param {number[]} arr - 需要堆排序的数组 
 */
export function heapSort(arr) {
  insertHeap(arr); // 构建堆
  let end = arr.length - 1; // 数组结束下标
  while (end >= 1) {
    swap(arr, 0, end);
    end--;
    correctHeap(arr, 0, end); // 纠正堆
  }
}

/**
 * @description 自下而上的堆排序
 * @param {*} arr - 需要堆排序的数组
 */
export function heapSort2(arr) {
  // 构建堆
  let end = arr.length - 1;
  let cur = (end - 1) >> 1; // 最后一个非叶子节点
  while (cur >= 0) {
    correctHeap(arr, cur, end);
    cur--;
  }
  // 纠正堆
  while (end >= 1) {
    swap(arr, 0, end);
    end--;
    correctHeap(arr, 0, end); // 纠正堆
  }
}