【Day18】[资料结构]-堆积Heap-实作

堆积(Heap)建立的方法(以最大堆积实作)

maxHeapify: 最大堆积化
push: 新增元素
pop: 删除特定元素
popRoot: 删除根节点(最大值)
getRoot: 查看根节点(最大值)
printHeap: 印出最大堆积

堆积的介绍可以参考此篇。

JavaScript

//MaxHeap
class MaxHeap{
  constructor(){
    this.list = [];
  }
  
  //最大堆积化
  maxHeapify = (arr, n, i) => {
    let largest = i;
    let l = 2 * i + 1;
    let r = 2 * i + 2;
     if (l < n && arr[l] > arr[largest]) {
           largest = l; 
     }
     if (r < n && arr[r] > arr[largest]) {
          largest = r; 
     }
     if (largest != i) { 
        [arr[i],arr[largest]] = [arr[largest],arr[i]];
        this.maxHeapify(arr, n, largest); 
      } 
  }
  
  //新增元素
  push = (num) => {
    const size = this.list.length;
    if(size === 0){
      this.list.push(num);
    }else{
      this.list.push(num);
      for (let i = parseInt(this.list.length / 2 - 1); i >= 0; i--) {
         this.maxHeapify(this.list, this.list.length, i); 
      }
    }
  }
  
  //删除元素
  pop = (num) => {
    const size = this.list.length;
    
    let i;
    for(i = 0; i < size; i++){
      if(num === this.list[i]){
        break;
      }
    }
    
    //要删除元素与最後一个元素交换
    [this.list[i], this.list[size - 1]] = [this.list[size - 1], this.list[i]];
    
    //删除最後一个元素
    this.list.splice(size - 1);
    
    for (let i = parseInt(this.list.length / 2 - 1); i >= 0; i--) {
         this.maxHeapify(this.list, this.list.length, i); 
     }
  }
  
  //回传最大值
  getRoot = () => this.list[0];
  
  //删除最大值
  popRoot = () => {
    this.pop(this.list[0]);
  }
  
  //印出最大堆积
  printHeap = () => this.list;
}

let heap = new MaxHeap()
heap.push(20)
heap.push(10)
heap.push(5)
heap.push(80)
heap.push(75)
heap.push(78)
heap.push(72)
heap.push(73)
console.log(heap.printHeap())//80, 75, 78, 73, 20, 5, 72, 10
heap.popRoot()
console.log(heap.printHeap())//78, 75, 72, 73, 20, 5, 10

Python

heapq是能实现Heap结构的套件，Python满多会使用此种作法，只不过在删除元素时，似乎只有把最小/大值删除的方法，这应该是因为用Heap来达到优先伫列(Priority Queue)的需求，权重最高的根节点会优先处理，後进先出的概念。

#MaxHeap
import heapq
class MaxHeap:
    def __init__(self):
        self.maxheap = []

    def push(self, key):
        heapq.heappush(self.maxheap, key)
        heapq._heapify_max(self.maxheap)

    def getRoot(self):
        return self.maxheap[0]

    def popRoot(self):
        heapq.heappop(self.maxheap)
        heapq._heapify_max(self.maxheap)

    def printHeap(self):
        print(self.maxheap)

heap = MaxHeap()
heap.push(20)
heap.push(10)
heap.push(5)
heap.push(80)
heap.push(75)
heap.push(78)
heap.push(72)
heap.push(73)
heap.printHeap()#80, 75, 78, 73, 20, 5, 72, 10
heap.popRoot()
heap.printHeap()#78, 75, 72, 73, 20, 5, 10
heap.popRoot()
heap.printHeap()#75, 73, 10, 72, 20, 5