请选择 进入手机版 | 继续访问电脑版
搜索
房产
装修
汽车
婚嫁
健康
理财
旅游
美食
跳蚤
二手房
租房
招聘
二手车
教育
茶座
我要买房
买东西
装修家居
交友
职场
生活
网购
亲子
情感
龙城车友
找美食
谈婚论嫁
美女
兴趣
八卦
宠物
手机

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

[复制链接]
查看: 75|回复: 0

2万

主题

2万

帖子

7万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
70839
发表于 2020-1-15 09:15 | 显示全部楼层 |阅读模式
一、大/小根堆成员属性:机关函数第二个参数决议大根堆与小根堆

可以利用根堆求解巨细位置的数组中前i大大概前i小的元素,也可以将其举行按巨细排序。
道理与特点:利用完全二叉树的父子结点在线性表中的索引关系,较为高效的利用空间去实现树形结构,并到达相关要求。这里以索引值 1 为堆顶元素索引作为展开。
  为了更好的去利用巨细根堆,采取标志参数:max_heap和min_heap来实现巨细根堆的切换,更好的低落了代码量,同时也能尽管连结功用的完整与尝试的高效。
  (不完竣的地方:应当改良寄存容器方式,制止容器的再哈希发生不必要的时候开销,可以在机关工具的时候就肯定容器的巨细)
  1. 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
  2. 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_heap24         };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. 1 template2 void heap
  2. ::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.弹出元素:
  1. templateP heap
  2. ::pop(){    this->Delete(0);    return getTop()*maxmin_heap;}
复制代码
3.删除元素:
用堆底元素更换,并经过下沉调解,使其公道
[code] 1 template 2 void heap
::Delete(int i){ 3     if(i>heap_count) return; 4     cout
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Copyright © 2006-2014 淄博新闻网-淄博日报 淄博晚报 淄博财经新报 掌中淄博 淄博专业新闻资讯发布网站 版权所有 法律顾问:高律师 客服电话:0791-88289918
技术支持:迪恩网络科技公司  Powered by Discuz! X3.2
快速回复 返回顶部 返回列表