日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

using System;
using System.Collections.Generic;
namespace Skyiv.Util
{
   class PriorityQueue
      
       
  {
       
    IComparer
       
         comparer;
        
    T[] heap; 
       
     
    public int Count { get; private set; }
    public PriorityQueue() : this(null) { }
    public PriorityQueue(int capacity) : this(capacity, null) { }
    public PriorityQueue(IComparer
      
        comparer) : this(16, comparer) { } 
     
    public PriorityQueue(int capacity, IComparer
      
        comparer)
       
    {
       
      this.comparer = (comparer == null) ? Comparer
       
        .Default : comparer;
        
      this.heap = new T[capacity];
        
    } 
       
     
    public void Push(T v)
    {
      if (Count >= heap.Length) Array.Resize(ref heap, Count * 2);
      heap[Count] = v;
      SiftUp(Count++);
    }
    public T Pop()
    {
      var v = Top();
      heap[0] = heap[--Count];
      if (Count > 0) SiftDown(0);
      return v;
    }
    public T Top()
    {
      if (Count > 0) return heap[0];
      throw new InvalidOperationException("優(yōu)先隊(duì)列為空");
    }
    void SiftUp(int n)
    {
      var v = heap[n];
      for (var n2 = n / 2; n > 0 && comparer.Compare(v, heap[n2]) > 0; n = n2, n2 /= 2)
        heap[n] = heap[n2];
      heap[n] = v;
    }
    void SiftDown(int n)
    {
      var v = heap[n];
      for (var n2 = n * 2; n2 < Count; n = n2, n2 *= 2)
      {
        if (n2 + 1 < Count && comparer.Compare(heap[n2 + 1], heap[n2]) > 0) n2++;
        if (comparer.Compare(v, heap[n2]) >= 0) break;
        heap[n] = heap[n2];
      }
      heap[n] = v;
    }
  }
}