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

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;}};