# 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->找比他小的元素)
4. 有的話就和較大/小的孩子交換交換
(MaxHeap->和較大的換,MinHeap->和較小的換)
6. 重複第二步驟直到兩個子節點都比自己小

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. 否則就不換
=>符合堆的特徵