js实现最大堆

た入场券 2023-07-06 05:00 4阅读 0赞

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆：

*  shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。
 *  shiftDown(): 如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”。

shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 O(log n)。  
基于这两个原始操作还有一些其他的操作：

*  insert(value): 在堆的尾部添加一个新的元素，然后使用 shiftUp 来修复堆。
 *  remove(): 移除并返回最大值（最大堆）或者最小值（最小堆）。为了将这个节点删除后的空位填补上，需要将最后一个元素移到根节点的位置，然后使用 shiftDown 方法来修复堆。

有一个挺恶心人的地方就是JS的number数据类型会导致需要向下取整才能对heap数组进行上升操作，否则就会有小数点的情况。

let heap = [];
    function swap(index1, index2) {
        
      let temp;
      temp = heap[index1];
      heap[index1] = heap[index2];
      heap[index2] = temp;
    }
    function shiftup(index) {
        
      let parentIndex = (index - 1) >> 1// Math.floor((index - 1) / 2);
      if (index != 0 && heap[parentIndex] < heap[index]) {
        
        swap(parentIndex, index);
        shiftup(parentIndex);
      }
    }
    function shiftDown(index) {
        
      let leftNodeIndex = (index + 1) * 2 - 1, rightNodeIndex = (index + 1) * 2
      if (leftNodeIndex < heap.length && heap[leftNodeIndex] > heap[index]) {
        
        swap(leftNodeIndex, index);
        shiftDown(leftNodeIndex);
      } else if (rightNodeIndex < heap.length && heap[rightNodeIndex] > heap[index]) {
        
        swap(rightNodeIndex, index);
        shiftDown(rightNodeIndex);
      }
    }
    function insert(val) {
        
      heap.push(val);
      shiftup(heap.length - 1);
    }
    function remove() {
        
      swap(0, heap.length - 1);
      heap.pop();
      shiftDown(0);
      return heap[0];
    }
    insert(1);
    insert(3);
    insert(2);
    insert(5);
    remove();
    insert(4);
    insert(6);
    remove();
    console.log(heap);//[ 4, 3, 2, 1 ]

参考： [JavaScript实现 简易 堆][JavaScript_ _]

[JavaScript_ _]: https://www.cnblogs.com/qq965921539/p/11224551.html

发表评论取消回复

表情：

评论列表（有 0 条评论，4人围观）

还没有评论，来说两句吧...

相关阅读

相关最大堆的简单实现

一．什么是最大堆? 　　最大堆的每一个节点的值都大于它的子节点的值． ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_s

超、凢脫俗/ 2023年07月09日 02:08/ 0 赞/ 44 阅读

相关 js实现最大堆

有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆： shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节

た入场券/ 2023年07月06日 05:00/ 0 赞/ 5 阅读

相关最大堆，最小堆插入/删除以及最大堆的排序

先说一下最大堆如何排序：转自：http://www.cnblogs.com/luchen927/archive/2012/03/08/2381446.html 最大堆和最小堆

约定不等于承诺〃/ 2022年07月31日 16:15/ 0 赞/ 313 阅读

相关堆排序（最大堆）

基本概念数据结构：记录=关键值+卫星数据关键值：待排序的值卫星数据：与关键值一同存取原址排序：输入数组中仅有常数个（少量）元素需要在排序过程中存储在数组之外

我不是女神ヾ/ 2022年06月09日 12:25/ 0 赞/ 298 阅读

相关最大最小堆整理 & heapq最小最大堆

参考资料：关于堆排序的算法参考：[https://www.cnblogs.com/chengxiao/p/6129630.html][https_www.cnblogs.

待我称王封你为后i/ 2022年04月13日 06:13/ 0 赞/ 371 阅读

相关 python实现最大堆，最小堆和堆排序

目录 0.什么是堆 1.最大堆的实现 2.最小堆的实现 3.堆排序 0.什么是堆小堆和大堆分为如下图： ![2018091712014232][] > 堆

电玩女神/ 2022年02月20日 14:17/ 0 赞/ 549 阅读

相关最大堆、最小堆Java实现，解决TOP K问题

一、基础知识 1.1 什么是最大（小）堆最大堆，最小堆类似，以下以最小堆为例进行讲解。最小堆是满足以下条件的数据结构： 1. 它是一棵完全二叉树 2.

今天药忘吃喽~/ 2022年01月30日 18:23/ 0 赞/ 382 阅读

相关使用PriorityQueue来实现最大堆

题目：最小的k个数输入n个整数，找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。主要思路：使用最大堆，保存

朴灿烈づ我的快乐病毒、/ 2021年10月30日 04:14/ 0 赞/ 310 阅读

相关最大堆(Java数组实现)

最大堆 data\[1\]开始存，data\[0\]空着不用。也可以把data\[0\]当成size来用。 public class MaxHeap<T

￡神魔★判官ぃ/ 2021年10月23日 07:23/ 0 赞/ 307 阅读

相关堆排序最大堆最小堆

package com.tree; import java.text.SimpleDateFormat; import java.util.Arrays

￡神魔★判官ぃ/ 2021年10月15日 02:49/ 0 赞/ 430 阅读