Posted on 2012-11-19 21:09
鑫龍 閱讀(1209)
評論(1) 編輯 收藏 引用 所屬分類:
數據結構與算法
最小堆：
template<class T>
class MinHeap {
public:
MinHeap(int MinHeapSize = 10);
~MinHeap() {delete [] heap;}
int Size() const {return CurrentSize;}
T Min() {if (CurrentSize == 0)
throw OutOfBounds();
return heap[1];}
MinHeap<T>& Insert(const T& x);
MinHeap<T>& DeleteMin(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>
MinHeap<T>::MinHeap(int MinHeapSize)
{
MaxSize = MinHeapSize;
heap = new T[MaxSize+1];
CurrentSize = 0;
}
template<class T>
MinHeap<T>& MinHeap<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>
MinHeap<T>& MinHeap<T>::DeleteMin(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 MinHeap<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 MinHeap<T>::Output() const
{
cout << "The " << CurrentSize
<< " elements are"<< endl;
for (int i = 1; i <= CurrentSize; i++)
cout << heap[i] << ' ';
cout << endl;
}
最大堆:
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;
}