Heap

堆(heap)
應用: Priority Queue



int Maxheap[1000];
int tail=0; //紀錄最尾端

把元素放進堆裡

  1. 放到最尾端
  2. 往上找他的祖先沒有比他大/小的元素
  3. 有的話就交換
  4. 重複第二步驟直到符合堆的特徵









void insert(int val){
  Maxheap[++tail]=val;
  int now=tail;
  while(now/2>0&&Maxheap[now/2]<Maxheap[now]){
    swap(now/2,now);
    now/=2;
  }
}

把最頂端的元素拿出來

  1. 把最後一個元素拿到頂端
  2. 往下找他的小孩有沒有比他大/小的元素
    (MaxHeap->找比他大的元素,MinHeap->找比他小的元素)
  3. 有的話就和較大/小的孩子交換交換
    (MaxHeap->和較大的換,MinHeap->和較小的換)
  4. 重複第二步驟直到兩個子節點都比自己小


















void delet(){
  Maxheap[1]=Maxheap[tail--];
  int now=1;
  while(1){
      if(now*2==tail && heap[now]<heap[now*2]){
          swap(now,now*2);
          now=now*2;
      }else if(now*2<tail && heap[now]<heap[now*2] && heap[now*2]>=heap[now*2+1]){
          swap(now,now*2);
          now=now*2;
      }else if(now*2+1<=tail && heap[now]<heap[now*2+1] && heap[now*2+1]>heap[now*2]){
          swap(now,now*2+1);
          now=now*2+1;
      }else{
          break;
      }
  }
}

在while裡面有4種情況

  1. 如果now的左小孩是最後一個且比now大
    =>那就跟左小孩換(此為必免第2點在判斷時超出邊界)
  2. 如果now的左小孩比now大且比右小孩大
    =>那就跟左小孩換
  3. 如果now的右小孩比now大且比左小孩大
    =>那就跟右小孩換
  4. 否則就不換
    =>符合堆的特徵
Select a repo