谁能帮我看看我的堆排序~~~！

谁能帮我看看我的堆排序~~~！

我看了一遍你的程序，感觉堆的数据结构你没有体现出来。
所以我找了一个我们课本上的源程序，你看看行不行。

#include
#include

template
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& Insert(const T& x);
MaxHeap& DeleteMax(T& x);
void Initialize(T a[], int size, int ArraySize);
void Deactivate() {heap = 0;}
void Output() const;
private:
int CurrentSize, MaxSize;
T *heap; // element array
};

template
MaxHeap::MaxHeap(int MaxHeapSize)
{// Max heap constructor.
MaxSize = MaxHeapSize;
heap = new T[MaxSize+1];
CurrentSize = 0;
}

template
MaxHeap& MaxHeap::Insert(const T& x)
{// Insert x into the max heap.
// find place for x
// i starts at new leaf and moves up tree
int i = ++CurrentSize;
while (i != 1 && x > heap[i/2]) {
// cannot put x in heap[i]
heap[i] = heap[i/2]; // move element down
i /= 2; // move to parent
}

heap[i] = x;
return *this;
}

template
MaxHeap& MaxHeap::DeleteMax(T& x)
{// Set x to max element and delete
// max element from heap.
// check if heap is empty
if (CurrentSize == 0)
return *this; // empty

x = heap[1]; // max element

// restucture heap
T y = heap[CurrentSize--]; // last element

// find place for y starting at root
int i = 1, // current node of heap
ci = 2; // child of i
while (ci <= CurrentSize) {
// heap[ci] should be larger child of i
if (ci < CurrentSize &&
heap[ci] < heap[ci+1]) ci++;

// can we put y in heap[i]?
if (y >= heap[ci]) break; // yes

// no
heap[i] = heap[ci]; // move child up
i = ci; // move down a level
ci *= 2;
}
heap[i] = y;

return *this;
}

template
void MaxHeap::Initialize(T a[], int size,
int ArraySize)
{// Initialize max heap to array a.
delete [] heap;
heap = a;
CurrentSize = size;
MaxSize = ArraySize;

// make into a max heap
for (int i = CurrentSize/2; i >= 1; i--) {
T y = heap[i]; // root of subtree

// find place to put y
int c = 2*i; // parent of c is target
// location for y
while (c <= CurrentSize) {
// heap[c] should be larger sibling
if (c < CurrentSize &&
heap[c] < heap[c+1]) c++;

// can we put y in heap[c/2]?
if (y >= heap[c]) break; // yes

// no
heap[c/2] = heap[c]; // move child up
c *= 2; // move down a level
}
heap[c/2] = y;
}
}

template
void MaxHeap::Output() const
{
cout << "The " << CurrentSize
<< " elements are"<< endl;
for (int i = 1; i <= CurrentSize; i++)
cout << heap[i] << ' ';
cout << endl;
}

template
void HeapSort(T a[], int n)
{// Sort a[1:n] using the heap sort method.
// create a max heap of the elements
MaxHeap H(1);
H.Initialize(a,n,n);

// extract one by one from the max heap
T x;
for (int i = n-1; i >= 1; i--) {
H.DeleteMax(x);
a[i+1] = x;
}

// save array a from heap destructor
H.Deactivate();
}

void main(void)
{
int a[11], i, n = 10;
// 测试数据
for (i = 1; i <= 10; i++)
a[i] = n - i + 1;

HeapSort(a,10);

// 输出结果
for (i = 1; i <= n; i++)
cout << a[i] << ' ';
cout << endl;
}

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息