判断以下序列是否是最小二叉堆堆？如果不是，将...

来源：蜘蛛抓取(WebSpider) 时间：2011-10-23 08:43 标签： 最小二叉堆
已知一关键码序列为:15,13,20,18,12,60.建立最小堆的过程 (每趟的序列)_百度知道
已知一关键码序列为:15,13,20,18,12,60.建立最小堆的过程 (每趟的序列)
提问者采纳
15 12 20 18 13 6012
15 20 18 23 6012
13 20 18 15 60
提问者评价
其他类似问题
楼下是正确答案，我就说说方法：1.先将上面数据按层次写成二叉树形式。2.再从最后一个非终结点开始，判断其与左右孩子的大小，将三者中最小的放到当前节点
依次往前推，执行到根节点结束。看看算法导论，相信你会学到很多。
最小堆的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁1582人阅读
#ifndef _MINHEAP_H
#define _MINHEAP_H
template &class T&
class MinHeap
//最小堆ADT定义
//存放堆数据的数组
int CurrentS //当前堆中元素数目
//堆所能容纳的最大元素数目
void BuildHeap(); //建堆
//构造函数,n表示初始化堆的最大元素数目
MinHeap(const int n,const T* array, int size);
//析构函数
virtual ~MinHeap()
delete []heapA
//如果是叶结点，返回TRUE
bool isLeaf(int pos)
//返回左孩子位置
int leftchild(int pos)
//返回右孩子位置
int rightchild(int pos)
// 返回父结点位置
int parent(int pos)
// 删除给定下标的元素
bool Remove(int pos, T& node);
//向堆中插入新元素newNode
bool Insert(const T& newNode);
//从堆顶删除最小值
T& RemoveMin();
//从position向上开始调整，使序列成为堆
void SiftUp(int position);
//筛选法函数，参数left表示开始处理的数组下标
void SiftDown(int left);
template&class T&
MinHeap&T&::MinHeap(const int n,const T* array, int size)
if(n&=0||size&n)
CurrentSize=0;
MaxSize=n;//初始化堆容量为n
heapArray=new T[MaxSize];//创建堆空间
//此处进行堆元素的赋值工作
//要为heapArray数组进行一些赋值，不然
//无法实现建堆操作，因为CurrentSize为0
for(int i=0; i& i++)
heapArray[i]=array[i];
CurrentSize =
BuildHeap();
template&class T&
void MinHeap&T&::BuildHeap()
//反复调用筛选函数，问题：CurrentSize&2?
for (int i=CurrentSize/2-1; i&=0; i--)
SiftDown(i);
//筛选法函数，参数left表示开始处理的数组下标
template &class T&
void MinHeap&T&::SiftDown(int position)
int i=//标识父结点
//此时j不一定是关键值较小的子结点，
//但是希望它标识关键值较小的子结点。
int j=2*i+1;
T temp=heapArray[i];//保存父结点
while(j&CurrentSize){
if((j&CurrentSize-1)&&(heapArray[j]&heapArray[j+1]))
//while第一次循环时，如果进入，比较左结点和右结点的值
//如果左结点的值大于右结点的值则，j指向数值较小的子结点
if(temp&heapArray[j]){
heapArray[i]=heapArray[j];
j=2*j+1;//向下继续
heapArray[i]=
//如果是叶结点，返回TRUE
template&class T&
bool MinHeap&T&::isLeaf(int pos) const
return (pos&=CurrentSize/2)&&(pos&CurrentSize);
//返回左孩子位置
template&class T&
int MinHeap&T&::leftchild(int pos) const
return 2*pos+1;//返回左孩子位置
//返回右孩子位置
template&class T&
int MinHeap&T&::rightchild(int pos) const
return 2*pos+2;//返回右孩子位置
// 返回父结点位置
template&class T&
int MinHeap&T&::parent(int pos) const
return (pos-1)/2;//返回父结点位置
//向堆中插入新元素newNode
template &class T&
bool MinHeap&T&::Insert(const T& newNode)
if(CurrentSize == MaxSize)//堆空间已经满
heapArray[CurrentSize]=newN
SiftUp(CurrentSize);//向上调整
CurrentSize++;
//从position向上开始调整，使序列成为堆
template&class T&
void MinHeap&T&::SiftUp(int position)
int temppos=
T temp=heapArray[temppos];
//请比较父子结点直接swap的方法
while((temppos&0)&&(heapArray[parent(temppos)]&temp))
heapArray[temppos]=heapArray[parent(temppos)];
temppos=parent(temppos);
heapArray[temppos]=
//从堆顶删除最小值
template&class T&
T& MinHeap&T&::RemoveMin()
if(CurrentSize==0)
cout&&&Can't Delete&;
//交换堆顶和最后一个元素
swap(0,--CurrentSize);
if(CurrentSize&1)
// &=1就不要调整了
//从堆顶开始筛选
SiftDown(0);
return heapSize[CurrentSize];
}//end else
// 删除给定下标的元素
template&class T&
bool MinHeap&T&::Remove(int pos, T& node)
{// 删除给定下标的元素
if((pos&0)||(pos&=CurrentSize))
//指定元素置于最后
T temp=heapArray[pos];
heapArray[pos]=heapArray[--CurrentSize];
SiftUp(pos);//上升筛
SiftDown(pos);//向下筛，不是SiftDown(0);
#include &MinHeap.h&
#include &stdio.h&
void main()
int array[10]={10,9,8,7,6,5,4,3,2,1};
MinHeap&int&* heap = new MinHeap&int&(20,array,10);
int node = 4;
heap-&Insert(node);
heap = NULL;
//参考北京大学张铭ppt
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：36737次
排名：千里之外
原创：31篇
转载：13篇
评论：13条
(5)(1)(1)(33)(4)收藏，1k 浏览
问题对人有帮助，内容完整，我也想知道答案
问题没有实际价值，缺少关键内容，没有改进余地
外部排序的介绍，参考资料：。
实际上，中文wiki上的介绍中，直接使用了最小堆来做排序后的多个子文件的归并，以得到最终的排序序列。而在我看到的很多网上资料上，却是介绍使用败者树，比如如下链接： 、
按照我的理解，最小堆实现和败者树实现理应在时间复杂度和空间复杂上差不多（虽然败者树需要额2k的空间，而最小堆本身只需要k的空间，但最小堆每个元素被取出后，还需要确定是从哪个顺串中补充元素，故也需要增加额外的空间标记堆中元素所在的顺串），这两者有什么区别呢，或者如何选择？
实际上，我在网上查阅败者树的资料时，并没有找到英文资料-,-，让我很费解。请大家赐教~
回答，投票，评论
第三方账号登录，无需注册，即刻开始
举报理由：
带有人身攻击、辱骂、仇恨等违反条款的内容
与已有问题重复
内容质量差，或不适合在本网站出现
答非所问，不符合答题要求
其他原因（请补充说明）
补充说明：数据结构考试卷_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
评价文档：
12页免费7页免费7页免费5页免费1页免费 6页免费9页2下载券4页2下载券3页免费17页1下载券
喜欢此文档的还喜欢9页2下载券7页1下载券12页免费169页1下载券50页免费
数据结构考试卷|数​据​结​构​考​试​卷
把文档贴到Blog、BBS或个人站等：
普通尺寸(450*500pix)
较大尺寸(630*500pix)
你可能喜欢

我要回帖

更多关于 最小二叉堆 的文章

 

随机推荐