最大堆

鎖定

template<class T>
class MaxHeap {
public:
    MaxHeap(int MaxHeapSize = 10);
    ~MaxHeap() {delete [] heap;}
    int Size() const {return CurrentSize;}
    T Max() {if (CurrentSize == 0)
              throw OutOfBounds();
           return heap[1];}
    MaxHeap<T>& Insert(const T& x);
    MaxHeap<T>& DeleteMax(T& x);
    void Initialize(T a[], int size, int ArraySize);
    void Deactivate() {heap = 0;}
    void Output() const;
private:
    int CurrentSize, MaxSize;
    T *heap;
};
template<class T>
MaxHeap<T>::MaxHeap(int MaxHeapSize)
{
    MaxSize = MaxHeapSize;
    heap = new T[MaxSize+1];
    CurrentSize = 0;
}
template<class T>
MaxHeap<T>& MaxHeap<T>::Insert(const T& x)
{
    if (CurrentSize == MaxSize)
        throw NoMem();
    //為x尋找應插入的位置
    //i從新的葉節點開始，並沿着樹上升
    int i = ++CurrentSize;
    while (i != 1 && x > heap[i/2]) 
    {
        heap[i] = heap[i/2]; // 將元素下移
        i /= 2;              // 移向父節點
    }
    heap[i] = x;
    return *this;
}
template<class T>
MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x)
{
    if (CurrentSize == 0)
        throw OutOfBounds();
    x = heap[1];
    T y = heap[CurrentSize--]; //最後一個元素
    // 從根開始, 為y尋找合適的位置
    int i = 1,  // 堆的當前節點
       ci = 2;    // i的子節點
    while (ci <= CurrentSize)
    {
        // 使heap[ci] 是i較大的子節點
        if (ci < CurrentSize 
         && heap[ci] < heap[ci+1]) 
            ci++;
        // 能把y放入heap[i]嗎?
        if (y >= heap[ci]) 
            break;//能
        //不能
        heap[i] = heap[ci]; // 子節點上移
        i = ci;             // 下移一層
        ci *= 2;
    }
    heap[i] = y;
    return *this;
}
template<class T>
void MaxHeap<T>::Initialize(T a[], int size, int ArraySize)
{
    delete [] heap;
    heap = a;
    CurrentSize = size;
    MaxSize = ArraySize;
    // 產生一個最大堆
    for (int i = CurrentSize/2; i >= 1; i--) 
    {
        T y = heap[i]; // 子樹的根
        // 尋找放置y的位置
        int c = 2*i; // c 的父節點是y的目標位置
                
        while (c <= CurrentSize) 
        {
            // 使heap[c]是較大的子節點
            if (c < CurrentSize 
             && heap[c] < heap[c+1])
                c++;
            // 能把y放入heap[c/2]嗎?
            if (y >= heap[c]) 
                break;  // 能
            // 不能
            heap[c/2] = heap[c]; // 子節點上移
            c *= 2;                 // 下移一層
        }
        heap[c/2] = y;
    }
}
template<class T>
void MaxHeap<T>::Output() const
{
   cout << "The " << CurrentSize 
        << " elements are"<< endl;
   for (int i = 1; i <= CurrentSize; i++)
       cout << heap[i] << ' ';
   cout << endl;
}