[数据结构]用JavaScript实现一个堆类

柔光的暖阳◎ 2022-12-12 04:40 158阅读 0赞

#### 前言: ####

在js中是没有堆这个数据结构的，但我们可以用类和Array模拟一个堆

#### 实现步骤: ####

· 在类里，声明一个数组，用来装元素。  
· 主要方法：插入、删除堆顶、获取堆顶、获取堆大小。

#### CODE:（以最小堆为例） ####

class MinHeap { 
          constructor() { 
            this.heap = []
          }
          swap(i1, i2) { 
            [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]]
          }
          getParentIndex(i) { 
            return (i - 1) >> 1 // 相当于Math.floor((i - 1) / 2)
          }
          getLeftIndex(i) { 
            return i * 2 + 1
          }
          getRightIndex(i) { 
            return i * 2 + 2
          }
          shiftUp(index) { 
            if (index === 0) { 
              return
            }
            const parentIndex = this.getParentIndex(index)
            if (this.heap[parentIndex] > this.heap[index]) { 
              this.swap(parentIndex, index);
              this.shiftUp(parentIndex)
            }
          }
          shiftDown(index) { 
            const leftIndex = this.getLeftIndex(index)
            const rightIndex = this.getRightIndex(index)
            if (this.heap[leftIndex] < this.heap[index]) { 
              this.swap(leftIndex, index)
              this.shiftDown(leftIndex)
            }
            if (this.heap[rightIndex] < this.heap[index]) { 
              this.swap(rightIndex, index)
              this.shiftDown(rightIndex)
            }
          }
          insert(value) { 
            this.heap.push(value)
            this.shiftUp(this.heap.length - 1)
          }
          pop() { 
            this.heap[0] = this.heap.pop() // 将最后一位pop并且赋值给堆顶
            this.shiftDown(0)
          }
          peek() { 
            return this.heap[0]
          }
          size() { 
            return this.heap.length
          }
        }
    
        const h = new MinHeap()
        h.insert(3)
        h.insert(2)
        h.insert(1)
        h.pop()
        console.log(h.peek())
        console.log(h.size())
        console.log(h)