首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在Javascript中实现递归maxHeap

在JavaScript中实现递归的最大堆(maxHeap)可以通过以下代码实现:

代码语言:txt
复制
function maxHeapify(arr, n, i) {
  let largest = i; // 初始化最大值为当前节点
  const left = 2 * i + 1; // 左子节点的索引
  const right = 2 * i + 2; // 右子节点的索引

  // 如果左子节点大于根节点,更新最大值
  if (left < n && arr[left] > arr[largest]) {
    largest = left;
  }

  // 如果右子节点大于根节点,更新最大值
  if (right < n && arr[right] > arr[largest]) {
    largest = right;
  }

  // 如果最大值不是当前节点,交换最大值和当前节点
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    // 递归调用maxHeapify函数,继续向下调整最大堆
    maxHeapify(arr, n, largest);
  }
}

function buildMaxHeap(arr) {
  const n = arr.length;
  // 从最后一个非叶子节点开始,依次向上构建最大堆
  for (let i = Math.floor(n / 2) - 1; i >= 0; i--) {
    maxHeapify(arr, n, i);
  }
}

function heapSort(arr) {
  const n = arr.length;
  // 构建最大堆
  buildMaxHeap(arr);

  // 从最后一个节点开始,依次将最大值交换到数组末尾,并重新调整堆
  for (let i = n - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    maxHeapify(arr, i, 0);
  }

  return arr;
}

// 示例用法
const arr = [4, 10, 3, 5, 1];
const sortedArr = heapSort(arr);
console.log(sortedArr); // 输出 [1, 3, 4, 5, 10]

这段代码实现了递归的最大堆排序算法。首先,maxHeapify函数用于调整以某个节点为根的子树,使其满足最大堆的性质。buildMaxHeap函数用于构建最大堆,从最后一个非叶子节点开始,依次调用maxHeapify函数。最后,heapSort函数使用构建好的最大堆进行排序,将最大值交换到数组末尾,并重新调整堆。

这个算法的时间复杂度为O(nlogn),其中n是数组的长度。它可以用于对任意类型的数据进行排序。

腾讯云相关产品和产品介绍链接地址:

  • 云服务器(CVM):https://cloud.tencent.com/product/cvm
  • 云数据库 MySQL 版(CDB):https://cloud.tencent.com/product/cdb
  • 云函数(SCF):https://cloud.tencent.com/product/scf
  • 人工智能平台(AI Lab):https://cloud.tencent.com/product/ailab
  • 云存储(COS):https://cloud.tencent.com/product/cos
  • 区块链服务(BCS):https://cloud.tencent.com/product/bcs
  • 物联网开发平台(IoT Explorer):https://cloud.tencent.com/product/explorer
  • 移动推送(信鸽):https://cloud.tencent.com/product/tpns
  • 视频处理(云点播):https://cloud.tencent.com/product/vod
  • 音频处理(语音识别):https://cloud.tencent.com/product/asr
  • 网络安全(天御):https://cloud.tencent.com/product/dsa
  • 云原生应用引擎(TKE):https://cloud.tencent.com/product/tke
  • 元宇宙(QingCloud):https://cloud.tencent.com/product/qingcloud
页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

领券