美文网首页
大顶堆(最大值)

大顶堆(最大值)

作者: 路灯下de男孩 | 来源:发表于2020-07-28 16:27 被阅读0次

[8,9,10,4,1,2,5,6,8,7,1]
结果
[9, 8, 10, 8, 7, 2, 5, 6, 4, 1, 1]
最大值终将在最左侧

function maxHeap (arr) {
  // 找到中间偏小位置树立标杆
  let st = Math.floor(arr.length / 2 - 1)
  // [0,1,2,3,4,5,6,7,8,9]
  // 从标杆位置遍历执行排序
  for (let i = st; i >= 0; i--) {
    sortMax(arr, i)
    console.log(arr)
  }
  console.log(arr)
  // 排序方法
  function sortMax (arr, i) {
    console.log(i)
    // 建立左侧值
    let left = i * 2 + 1
    // 建立右侧值
    let right = i * 2 + 2

    // 定义最大值下标
    let max = i
    // 判断左侧值是否存在,并且比默认值大
    if (arr[left] && arr[left] > arr[max]) {
          // 将最大值下标修改为left
          max = left
    }
    // 判断右侧值是否存在,是否比当前最大值大
    if (arr[right] && arr[right] > arr[max]) {
      // 将最大值下标修改为right
      max = right
    }
    // 如果最大值下标不是默认下标,将值替换
    if (max != i) {
      let s = arr[max]
      arr[max] = arr[i]
      arr[i] = s
      // 不能判断max是不是最大分支时
      sortMax(arr, max)
    }
  }
}

相关文章

  • 大顶堆(最大值)

    [8,9,10,4,1,2,5,6,8,7,1]结果[9, 8, 10, 8, 7, 2, 5, 6, 4, 1,...

  • 堆与堆排序

    堆(大顶堆)的概念 堆是一种特殊的二叉树,大顶堆就是根节点为最大值的堆,它具有如下的特点: 堆是完全二叉树 堆常用...

  • 经典排序算法系列6-堆排序

    Heap Sort-堆排序 以升序举例,将无序的序列构建成一个大顶堆(Heap),将堆顶元素(最大值)与序列中最后...

  • 堆调整算法

    堆调整算法 思路 算法将获取到一组数据的最大值(针对大顶堆)或最小值(针对小顶堆)。 基本思想 通过堆排序的调整算...

  • leetcode 天际线问题 python

    有点像滑动窗口找最大值。所以就类比地维护一个大顶堆,如果有新的可能性的天际线,就加到堆里。弹出最大值时要先检查他是...

  • 堆排序

    堆排序:将待排序的序列构造成一个大顶堆。此时,整个序列的最大值就是堆顶的根节点。将根节点与堆的末尾元素交换,此时末...

  • 大顶堆生成、新增、删除、排序javascript实现

    大顶堆小顶堆的概念和使用本文不赘述,使用js实现一个大顶堆的创建,新增,删除以及利用大顶堆排序

  • 剑指offer 数据流中的中位数

    建立大顶堆和小顶堆

  • 堆排序(java)

    将待排序序列构造成一个大顶堆,此时序列的最大值就是堆顶元素,将它和数组的末尾元素交换,再将剩余的n-1个元素构造成...

  • 堆-Heap

    堆-Heap 堆的基本接口设计 二叉堆(最大堆) 大顶堆-添加 大顶堆-删除 删除堆顶元素的同时插入一个新元素 大...

网友评论

      本文标题:大顶堆(最大值)

      本文链接:https://www.haomeiwen.com/subject/lqwfrktx.html