数据结构--大小根堆模板类

一、大/小根堆成员属性:构造函数第二个参数决定大根堆与小根堆

可以利用根堆求解大小位置的数组中前i大或者前i小的元素,也可以将其进行按大小排序。

原理与特点:利用完全二叉树的父子结点在线性表中的索引关系,较为高效的利用空间去实现树形结构,并达到相关要求。这里以索引值 1 为堆顶元素索引作为展开。

  为了更好的去使用大小根堆,采用标志参数:max_heap和min_heap来实现大小根堆的切换,更好的降低了代码量,同时也能尽量保持功能的完整与执行的高效。

  (不完善的地方:应该改进存放容器方式,避免容器的再哈希产生不必要的时间开销,可以在构造对象的时候就确定容器的大小)

 1 #include
 2 #include
 3 #include
 4 #include 
 5 #define Size long long
 6 using namespace std;
 7 template
 8 class heap{
 9     private:
10         Size heap_size;//容量限制 
11         Size heap_count;//数据计数 
12         vector

heap_elem;//堆容器 13 int maxmin_heap;//选择大\小根堆 14 15 void Up_adjust(int now);//上浮调整 16 void Down_adjust(P &top, int now);//下沉调整 17 public: 18 enum{max_heap=1, min_heap=-1}; 19 heap(Size s, int m=max_heap)://构造堆 20 heap_size(s){ 21 heap_count=0; 22 heap_elem.push_back(-999); 23 maxmin_heap=m;//default max_heap 24 }; 25 P getTop(){//弹获取堆顶元素 26 if(heap_count>0)return heap_elem[1]; 27 return heap_elem[0]*maxmin_heap; 28 } 29 bool empty(){//判断堆空 30 if(heap_count==0)return true; 31 return false; 32 } 33 void push(P x);//送元素入堆 34 P pop();//堆顶元素弹出 35 void Delete(int i);//删除第i个元素 36 void data();//打印堆 37 };

二、大小根堆成员函数:

1.插入元素:将新元素放入堆底,执行上浮调整,使其合理

1 template
2 void heap

::push(P x){ 3 ++heap_count; 4 heap_elem.push_back(x*maxmin_heap); 5 int now=heap_count; 6 Up_adjust(now); 7 if(heap_count>heap_size-1) 8 heap_count--; 9 }

2.弹出元素:

template
P heap

::pop(){ this->Delete(0); return getTop()*maxmin_heap; }

3.删除元素:

用堆底元素替换,并通过下沉调整,使其合理

 1 template
 2 void heap

::Delete(int i){ 3 if(i>heap_count) return; 4 cout << "delete heap["<< i <<"]: " << heap_elem[i]*maxmin_heap << endl; 5 if(i==heap_count){ 6 heap_count--; 7 return ;} 8 Down_adjust(heap_elem[heap_count],i); 9 heap_count--; 10 }

4.上浮调整:

1 template
2 void heap

::Up_adjust(int now){ 3 while(now>1 && heap_elem[now]>heap_elem[now/2]){ 4 std::swap(heap_elem[now], heap_elem[now/2]); 5 now=now/2; 6 } 7 }

5.下沉调整:

 1 template
 2 void heap

::Down_adjust(P &top, int now){ 3 heap_elem[now]=top; 4 int next1,next2; 5 while(now*2<=heap_count){ 6 if(now*2+1>heap_count){ 7 next1=next2=now*2; 8 } 9 else{ 10 next1 = heap_elem[now*2]>heap_elem[now*2+1] ? now*2 : now*2+1; 11 next2 = heap_elem[now*2]2+1] ? now*2 : now*2+1; 12 } 13 if(heap_elem[next1]>heap_elem[now]){ 14 swap(heap_elem[next1],heap_elem[now]); 15 now = next1; 16 } 17 else if(heap_elem[next2]>heap_elem[now]){ 18 swap(heap_elem[next2],heap_elem[now]); 19 now = next2; 20 } 21 else{ 22 break; 23 } 24 } 25 }

6.数据打印:

1 template
2 void heap

::data(){ 3 typename std::vector

::iterator itr=heap_elem.begin()+1; 4 cout << "heap[]: "; 5 for(int i=0;ii){ 6 cout << *(itr+i)*maxmin_heap << ' '; 7 } 8 cout << endl; 9 }

三、代码测试:以小根堆为例

可以注释掉标准输出语句,来减少执行操作的时间消耗,能更好测试大量数据插入、删除的实行时间。

 1 int main(){
 2     heap<int> h(20,heap<int>::min_heap);
 3     int x;
 4     srand(time(NULL));
 5     for(int i=0;i < 20;++i){
 6         x = rand()%1000;
 7         h.push(x);
 8         //h.data();
 9     }
10     h.data();
11     h.Delete(4);
12     while(!h.empty()){
13         h.pop();
14     }
15     cout << endl;
16     return 0;
17 }

数据结构--大小根堆模板类_第1张图片

你可能感兴趣的