关于如何实现一个堆的问题！

Question

实现一个堆最常用的方法包含在里面就可以了C语言写的 如果也有C++语言就更好了谢谢

Answer 1

貌似这个能帮你的忙。
#include <deque>

using namespace std;

enum HeapType...{MaxHeap, MinHeap};

template <class T, int capacity>
class Heap
...{

public:
Heap(HeapType type = MaxHeap)
...{
this->size = 0;
this->type = type;
this->Q.clear();
this->Q1.clear();
}

~Heap()...{}

int heap_insert(T& item)
...{
size++;
if(size > capacity)
...{
return -1;
}
/**//*
* 将item插到新的位置，然后对item作上升调整（交换元素）到合适的位置
* 即当item比它父亲小（最小堆）/大（最大堆）时，把item和它的父亲交换
*/
arr[size-1] = item;

return this->siftUp(size-1);
}

bool heap_del(int pos, T& result)
...{
if(pos < 0 || pos >= size)
...{
return false;
}

/**//*
* 用最后一个结点last把要删除的结点覆盖，再把last下降调整到合适的位置，即当last比它的某一个儿子大（最小堆）/小（最大堆）时，
* 把last和它的较小儿子（最小堆）/较大儿子（最大堆）交换
*/
result = arr[pos];
arr[pos] = arr[size-1];
size--;
this->siftDown(pos);
return true;
}

bool heap_delMax(T& result) //only valid for max heap
...{
if(type == MaxHeap)
...{
return this->heap_del(0, result);
}
else
...{
return false;
}
}

bool heap_delMin(T& result) //only valid for min heap
...{
if(type == MinHeap)
...{
return this->heap_del(0, result);
}
else
...{
return false;
}
}

bool find(T& item)
...{
bool found = false;

if(size > 0)
...{
Q.push_back(arr[0]);
Q1.push_back(0);

while(!Q.empty()&& !found)
...{
T q = Q.front();
int i = Q1.front();
int j = (i<<1) + 1;

if(q == item)
...{
found = true;
}
else if((this->type == MaxHeap? q > item : q < item))
...{
if(j < size)
...{
Q.push_back(arr[j]);
Q1.push_back(j);
}
if(j + 1 < size)
...{
Q.push_back(arr[j+1]);
Q1.push_back(j+1);
}
}

Q.pop_front();
Q1.pop_front();
}
}

return found;
}

void heap_sort()
...{
if(this->size <= 0)
...{
return;
}

int i;

for(i = this->size >> 1; i > 0; i--)
...{
this->siftDown(i-1);
}

int tsize = this->size;

while(this->size > 0)
...{
T temp = arr[0];
arr[0] = arr[this->size - 1];
arr[this->size - 1] = temp;
this->size--;
this->siftDown(0);
}

this->size = tsize;
}

protected:
T arr[capacity]; //完全二叉树.
int size; //arr[0..size-1]
HeapType type;
deque<T> Q;
deque<int> Q1;

int siftUp(int pos)
...{
int i = pos;
int j = ((i+1) >> 1) - 1;
T temp = arr[pos];

while(j >= 0 && ((type==MaxHeap) ? (arr[j] < temp):(arr[j] > temp)))
...{
arr[i] = arr[j];
i = j;
j = ((i+1) >> 1) - 1;
}

arr[i] = temp;

return i;
}

int siftDown(int pos)
...{
int i = pos;
int j = (i<<1) + 1;
bool finished = false;
T temp = arr[pos];

while(j < size && !finished)
...{
if(j + 1 < size && ((type == MaxHeap) ? (arr[j] < arr[j+1]):(arr[j] > arr[j+1])))
...{
j++;
}
if((type == MaxHeap) ? (temp >= arr[j]): (temp <= arr[j]))
...{
finished = true;
}
else
...{
arr[i] = arr[j];
i = j;
j = (i<<1) + 1;
}
}

arr[i] = temp;

return i;
}

};