建堆的算法

⑴ 求一计算机数据结构题解

以最大堆为例,给一个建堆的算法,
楼主要的保持堆的性质的算法,只要选取其中一段程序就行了~~~

//******************
// 6.3_1 建堆
// Date 2007.02.13
//******************

#include <iostream>
using namespace std;

const int maxn = 1000;

void max_heapify( int A[maxn], int i, int heap_size )
{
int l, r, largest, temp;

l = 2 * i;
r = 2 * i + 1;

if (( l <= heap_size ) && ( A[l] > A[i] ))
largest = l;
else
largest = i;
if (( r <= heap_size ) && ( A[r] > A[largest] ))
largest = r;
if ( largest != i ) {
temp = A[i];
A[i] = A[largest];
A[largest] = temp;

max_heapify( A, largest, heap_size );
}
}

void build_max_heap( int A[maxn], int n )
{
int i;

for (i = n / 2; i >= 1; i--)
max_heapify( A, i, n );
}

int main()
{
int i, n;
int A[maxn];

cin >> n;

for (i = 1; i <= n; i++)
cin >> A[i];

build_max_heap( A, n );

for (i = 1; i < n; i++)
cout << A[i] << ' ';

cout << A[n] << endl;

return 0;
}

⑵ 堆排序中建堆过程时间复杂度O(n)怎么来的

建堆算法是从最后一个非叶子结点开始下溯(即 Max-Heapify操作)，也可以把建堆过程想成先对左子树建堆(T(n/2))，再对右子树建堆(T(n/2))，最后对根下溯(O(lg n))

⑶ 堆排序是怎么建堆的 关键字序列 42 13 24 91 23 16 05 88是怎样建堆的

首先把所有数据填进一个完全二叉树中。然后对非终端结点n/2向下进行调整。建小根堆的时候方法是：1.元素下调。比较它与两个孩子的大小。哪个孩子比它小也比兄弟小则把它调到那个孩子的位置。然后再判断该位置还要不要往下调。2.从n/2开始，对它之前的所有元素进行1操作。
本题解法为（按完全二叉树写）
一。把所有元素写进完全二叉树中得
42
13 24
91 23 16 05
88

二。1.对非叶子元素进行调整，即第n/2个元素，即本题的91.
因为91的孩子为88.比91小。所以调到88的位置。即91和88换
42
13 24
88 23 16 05
91

2.对n/2前一个元素进行调整。即本题的24.因为16和05都比24小，而05比16小，所以24和05调
42
13 05
88 23 16 24
91

3.对步骤2之前的一个元素，即本题的13进行调整，因为88和23都比13大，所以不用调。
4.对步骤3之前的一个元素，即本题的42进行调整。因为13和05都比42小，二05比13小。所以05和42调换位置。而调换位置后42的儿子为16和24,16比24小。所以42和16换位置。（此时已经对第一个元素进行了调整，就可以结束了，如果没错的话就是最终结果）
05
13 16
88 23 42 24
91
建的是小根堆，如果要建大根堆的话，也是往下调，但比较的是下面的哪个大。其他同理

⑷ 如何判断一个序列是否为堆

堆可以看成一棵完全二叉树：

任一根节点>=左右孩子（或者<=）（大的叫大根堆，小的叫小根堆。）注意一个堆中的这种性质有一致性，不能既有大于又有小于情况存在。

这题你应该是理解错题意了，首先，大根堆是一个完全二叉树，根节点大于左右节点，利用堆的性质来看选项A：

91为根节点，下面挂两个子节点85、53。然后以85为根节点，下面挂两个子节点36、47，以53为根节点，下面挂两个子节点30，24。

以此类推，得到选项C是正确答案。

(4)建堆的算法扩展阅读：

堆是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：

1、堆中某个节点的值总是不大于或不小于其父节点的值；

2、堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。堆是线性数据结构，相当于一维数组，有唯一后继。

一、堆的算法思想

不必将值一个个地插入堆中，通过交换形成堆。假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能：

（1） R的值小于或等于其两个子女，此时堆已完成；

（2） R的值大于其某一个或全部两个子女的值，此时R应与两个子女中值较小的一个交换，结果得到一个堆，除非R仍然大于其新子女的一个或全部的两个。

这种情况下，我们只需简单地继续这种将R“拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。

二、堆的定义

堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。

(ki<= k2i,ki<= k2i+1)或者(ki>= k2i,ki>= k2i+1), (i = 1,2,3,4...n/2)

若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。

由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

⑸ 建堆的时间复杂度到底是多少

建最大堆或者最小堆都是O(N),不是O(NlogN)，这个证明在算法导论第3版 88页有证明。
建立完堆后，就开始交换堆顶元素和最后一个元素，叫做出堆，出堆后需要再次维护堆顶，这一步时间复杂度是logN。

⑹ 我看书上堆排序，每次都要重新建堆，然后再调外根节点和最后一个结点，感觉这样好麻烦你们是怎么做的呢

堆排序很重要的一个步骤是初始建堆，它保证了树中的每个子树的根结点都比其下的子结点大。
建堆后的过程基本上就是选择出最大值，然后将被交换到根结点位置的结点进行下沉的过程。而这些过程虽然对树的局部结构进行了调整，但严格来说，不算是重新建堆。
《算法导论》上对堆排序讲得很详细。它把堆排序算法分成了三个子算法：
一个将结点下沉的递归算法；一个初始建堆算法和一个排序算法。
具体过程是：
1、初始建堆算法调用结点下沉递归算法完成建堆；
2、排序算法在建好的堆上得到根结点(即最大值)，然后调用结点下沉的递归算法将交换到根结点位置的结点进行下沉。反复第2步，整个算法就完成了。
思路很清晰，可以去看看。

⑺ 为什么堆排序构建堆的时间复杂度是N,而重调堆的时间复杂度是logN

建堆的时候你看看是不是多次调用了调堆的函数呢，那肯定就不只是logN了，如果从底部最后的父节点开始建堆，那么我们可以大概算一下：
假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2^(H-1)个,倒数第二层公有2^(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。

⑻ 用一组｛14，15，30，28，5，10｝关键字序列，写出初始建堆过程图示，再根据初始堆写出堆排序过程图示。

起始序列为14，15，30，28，5，10，

(1)因此起始堆的情况如下：
14
15 30
28 5 10

(2)假设是打算得到一个从小到大的c，所以需要建大顶堆，起始状态从下向上建堆：
第一步： 第二步：
14 30
28 30 28 14
25 5 10 25 5 10

(3)此时已经建立完了初始的堆。此时堆顶元素30即为最大元素，将堆顶元素与堆最后
一个元素进行交换，此时30是最大元素位于队尾，因此无需继续排序。所以堆如下图
所示：10 28 14 25 5

(4)此时由于除被交换到堆顶的10以外其他的都基本有序，所以自上而下建堆得到的堆
如下：
28
25 14
10 5

(5)重复（3）和（4）步骤确定了28的位置并得到堆如下：
25
10 14
5

(6)重复（3）和（4）步骤确定了25的位置并得到堆如下：
14
10 5

(7)重复（3）和（4）步骤确定了14的位置并得到堆如下：
10
5

(8)重复（3）和（4）步骤确定了10的位置,此时只有一个数5也位于了堆的第一个位置，
因此排序完成。

(8)建堆的算法扩展阅读：

建堆效率

n个结点的堆，高度d =log2n。根为第0层，则第i层结点个数为2^i，考虑一个元素在堆中向下移动的距离。大约一半的结点深度为d-1，不移动（叶）。四分之一的结点深度为d-2，而它们至多能向下移动一层。树中每向上一层，结点的数目为前一层的一半，而子树高度加一。

这种算法时间代价为Ο（n)

由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是

Ο（log n）。

操作实现

在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作：

1.事先不知道程序所需对象的数量和大小。

2.对象太大，不适合使用堆栈分配器。

堆使用运行期间分配给代码和堆栈以外的部分内存。

传统上，操作系统和运行时库随附了堆实现。当进程开始时，操作系统创建称为进程堆的默认堆。如果没有使用其他堆，则使用进程堆分配块。

语言运行时库也可在一个进程内创建单独的堆。（例如，C 运行时库创建自己的堆。）除这些专用堆外，应用程序或许多加载的动态链接库 (DLL) 之一也可以创建并使用单独的堆。Win32 提供了一组丰富的API用于创建和使用专用堆。有关堆函数的优秀教程，请参阅 MSDN 平台 SDK 节点。