数据结构实现堆

缺乏、安全感 2022-11-22 00:21 120阅读 0赞

> 堆分类：最大堆、最小堆  
> 堆别名：优先队列  
> 堆应用：求topK，堆排序

1.  堆模板
    
        function Heap(_arr, _compareFunc){ 
          // 私有属性
          let heap = [];
          // 对象公有属性
          this.size = 0;
        
          // 私有方法
          // 计算左、右、父节点索引
          let left = () => { };
          let right = () => { };
          let parent = () => { };
          // 堆的shiftUp、shiftDown操作
          let shiftUp = () => { };
          let shiftDown = () => { };
          // 建堆函数
          let createHeap = () => { };
          // 对象公有方法
          this.insert = () => { };   // 插入新元素
          this.pop = () => { };      // 堆顶出堆
        	
          // 初始化操作
          console.error('未进行堆初始化');
          // 属性初始化
          // 建堆
        }
2.  堆简单实现
    
        function Heap(_arr, _compareFunc){ 
          /** * 堆 * @param {Array} _arr: 数组，注意传的是引用，建堆、insert、pop操作都会改变原数组 * @param {Function} _compareFunc: 比较函数，参数(a, b) * 元素为Number的最大堆，(a, b) => {return a-b;} * 元素为Number的最小堆，(a, b) => {return b-a;} */
          // 私有属性
          let heap = [];
        	
          // 对象公有属性
          this.size = 0;
        
          // 计算左、右、父节点
          let left = (_i) => { 
            return 2 * _i + 1;
          }
          let right = (_i) => { 
            return 2 * _i + 2;
          }
          let parent = (_i) => { 
            if(_i % 2 === 1) return (_i - 1) / 2;
            return (_i - 2) / 2;
          }
        
          // 私有函数
          let shiftUp = (_i) => { 
            /** * 堆的元素shiftUp操作 * 步骤： * 1. 判断当前结点与其父结点的位置是否正确，不正确的话则交换两各结点 * 2. 结点交换到父结点位置后继续递归进行shiftUp操作，直到位置正确或者到达堆顶 * @param {Number} _i: 要进行shiftUp的元素的索引 */
            let p = parent(_i);
            if(p >= 0){ 
              if(_compareFunc(heap[_i], heap[p]) > 0){ 
                [heap[_i], heap[p]] = [heap[p], heap[_i]]
              }
              shiftUp(p);
            }
          }
          let shiftDown = (_i) => { 
            /** * 堆的元素shiftDown操作 * 步骤： * 1. 当前结点与两个子节点中值最大(小)的结点比较，若当前结点位置不正确，则与子结点交换 * 2. 交换到子结点后继续递归进行shiftDown操作，直到其位置正确或到达叶节点 * @param {Number} _i: 要进行shiftDown的元素的索引 */
            let l = left(_i), r = right(_i);
            if(l < this.size && r < this.size){  // 左右孩子都存在
              let index = _compareFunc(heap[r], heap[l]) < 0 ? l: r;
              if (_compareFunc(heap[index], heap[_i]) > 0){ 
                [heap[_i], heap[index]] = [heap[index], heap[_i]];
                shiftDown(index);
              }
            }
            else if(l < this.size){  // 只有左孩子
              if (_compareFunc(heap[l], heap[_i]) > 0) { 
                [heap[_i], heap[l]] = [heap[l], heap[_i]];
                shiftDown(l);
              }
            }
            // 叶节点（完全二叉树，没有只有右孩子的情况）
          }
          let createHeap = (_root) => { 
            /** * 建堆函数 * 原理：假设当前结点的两个子树都是堆，那么对当前结点做shiftDown后，以当前为根结点的完全二叉树也完成了建堆 * 步骤：后续遍历二叉树，递归对两个子树进行建堆，再对当前结点进行 */
            let l = left(_root), r = right(_root);
            if(l < this.size){ 
              createHeap(l);
              if(r < this.size){   // 有左孩子的前提下才有可能有右孩子
                createHeap(r);
              }
              shiftDown(_root);
            }
          }
        
          // 对象公有方法
          this.insert = (_element) => { 
            /** * 往堆中插入结点 * 步骤：插入到堆尾，进行shiftUp */
            heap.push(_element);
            this.size++;
            shiftUp(this.size - 1);
          }
        
          this.pop = () => { 
            /** * 堆顶结点出堆 * 步骤：元素出堆，从堆尾取一元素放到堆顶，进行shiftDown */
            if(this.size > 0) { 
              let head = heap[0];
              this.size--;
              let tail = heap.pop();
              if (this.size > 0) { 
                heap[0] = tail;
                shiftDown(0);
              }
              return head;
            }
          }
        
          // 初始化
          heap = _arr;
          this.size = _arr.length;
          createHeap(0);	// 建堆
        
          // 测试用
          this.test = (_root) => { 
            // 先序遍历打印树结构，用于测试
            if(_root < this.size){ 
              console.log(heap[_root]);
              this.test(left(_root));
              this.test(right(_root));
            }
            else console.log('null')
          }
        }