请高手帮忙解释一道数据结构的试题,该怎么处理
请高手帮忙解释一道数据结构的试题
各位高手好!
本小弟马上要考数据结构了~ 看到一道习题
设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出发建堆的结果?( )
A. a,g,h,m,n,p,q,x,z B. a,g,m,h,q,n,p,x,z
C. g,m,q,a,n,p,x,h,z D. h,g,m,p,a,n,q,x,z
答案选的似乎是B
但是小弟不理解,希望高手帮忙~~谢谢~~
------解决方案--------------------
首先原始队列关键码也弄成完全2查树的样子,然后再调整使其成为一个堆
现在给你说一下建堆过程:
此题默认建的是个最小堆,答案没有最大堆
从第一个非叶接点开始,倒着来到跟节点,顺次进行调整(这是主函数)
现在介绍对每个节点的调整方法:向下调整法
比较根节点跟下面俩节点,如果根不是最小的,找出两个叶子里比较小的,跟根交换,交换完还不行,必须交换的那个节点递归向下调整,也就是跟下面俩叶子比较,直到没有可交换的或者到了叶节点停止~~~
不知道我这么说你能明白不
附上代码吧:
void MinHeap::BuildHeap()
{
//反复调用筛选函数,问题:CurrentSize=0; i--)
SiftDown(i);
}
void MinHeap <T> ::SiftDown(int left)
{
int i = left;
int j = leftchild(i);
T temp = heapArray[i];
while (j < CurrentSize)
{
if ((j < CurrentSize - 1) && (heapArray[j] > heapArray[j + 1]))
j ++;
if (temp > heapArray[j])
{
heapArray[i] = heapArray[j];
i = j;
j = leftchild(j);
}
else
break;
}
heapArray[i] = temp;
}
各位高手好!
本小弟马上要考数据结构了~ 看到一道习题
设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出发建堆的结果?( )
A. a,g,h,m,n,p,q,x,z B. a,g,m,h,q,n,p,x,z
C. g,m,q,a,n,p,x,h,z D. h,g,m,p,a,n,q,x,z
答案选的似乎是B
但是小弟不理解,希望高手帮忙~~谢谢~~
------解决方案--------------------
首先原始队列关键码也弄成完全2查树的样子,然后再调整使其成为一个堆
现在给你说一下建堆过程:
此题默认建的是个最小堆,答案没有最大堆
从第一个非叶接点开始,倒着来到跟节点,顺次进行调整(这是主函数)
现在介绍对每个节点的调整方法:向下调整法
比较根节点跟下面俩节点,如果根不是最小的,找出两个叶子里比较小的,跟根交换,交换完还不行,必须交换的那个节点递归向下调整,也就是跟下面俩叶子比较,直到没有可交换的或者到了叶节点停止~~~
不知道我这么说你能明白不
附上代码吧:
void MinHeap::BuildHeap()
{
//反复调用筛选函数,问题:CurrentSize=0; i--)
SiftDown(i);
}
void MinHeap <T> ::SiftDown(int left)
{
int i = left;
int j = leftchild(i);
T temp = heapArray[i];
while (j < CurrentSize)
{
if ((j < CurrentSize - 1) && (heapArray[j] > heapArray[j + 1]))
j ++;
if (temp > heapArray[j])
{
heapArray[i] = heapArray[j];
i = j;
j = leftchild(j);
}
else
break;
}
heapArray[i] = temp;
}