堆
堆是什么？
-
堆是一种特殊的
完全二叉树完全二叉树是指每层节点全部填满，最后一层如果不是满的，则只缺少右边的若干节点。 -
所有节点都大于等于（最大堆）或者小于等于（最小堆）它的子节点
最小堆
最大堆
JS中的堆
- js中通常用数组表示堆
- 左侧子节点的位置为2*index + 1
- 右侧子节点的位置为2*index + 2
- 父节点的位置是 Math.floor((index - 1) / 2)
堆的应用
- 堆能快速高效的找出最大值，最小值
- 时间复杂度为O(1)
- 找出第K个最大（小）元素
第K个最大元素
- 构建一个最小堆，并将元素依次插入堆中
- 当堆的容量超过K，就删除堆顶
- 插入结束后，堆顶就是第K个最大元素
點擊查看更多內容
為 TA 點贊
評論
評論
共同學習，寫下你的評論
評論加載中...
作者其他優質文章
正在加載中
感謝您的支持，我會繼續努力的～
掃碼打賞，你說多少就多少
贊賞金額會直接到老師賬戶
支付方式
打開微信掃一掃，即可進行掃碼打賞哦