在软件设计相关领域，“堆（Heap）”的概念主要涉及到两个方面： 一种是数据结构，逻辑上是一颗完全二叉树，存储上是一个数组对象（二叉堆）。 另一种是垃圾收集存储区，是软件系统可以编程的内存区域。 本文所说的堆指的是前者，另外，这篇文章中堆中元素的值均以整形为例 堆排序的时间复杂度是O(nlog2n),与快速排序达到相同的时间复杂度. 但是在实际应用中,我们往往采用快速排序... [阅读全文]

什么是堆？"堆"这个词最初是在堆排序中提出的，但后来就逐渐指"废料收集存储区"，当然这里不是指"废料收集存储区"。堆数据结构是一种数组对象，由于一棵完全二叉树可以用一组地址连续的存储单元依次自上而下、自左至右存储，故堆可以被视为一棵完全二叉树，如下图： 圆圈中的数字表示树中每个节点的值，节点上方的数字表示对应的数组下标。 一个堆的数组A，用length[A]表述数组中的元素个数，heap-siz... [阅读全文]

9.7.2 堆排序算法 堆排序（Heap Sort）就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根结点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次小值。如此反复执行，便能得到一个有序序列了。 例如图9-7-4，左图是一... [阅读全文]

9.7.1 堆结构介绍 我们前面讲到简单选择排序，它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解，查找第一个数据需要比较这么多次正常的，否则如何知道它是最小的记录。 可惜的是，这样的操作并没有把每一趟的比较结果保存下来，在后一趟的比较中，有许多比较在前一趟已经做过了，但由于前一趟排序时未保存这些比较结果，所以后一趟排序时又重复执行了这些比较操作，因而记录的比较次数较多。... [阅读全文]

上次提到了位图排序，这次主题也是排序，不过首先来点别的。 如何生成m个随机数？看了编程珠玑的文章，知道了一些，后来又在csdn上发现了其他人设计的，我就拿来说说吧。 如果没有头绪，那就按平常来说就是随机生成一个数，然后比较集合中是否存在，不存在放里面，否则再继续生成。按珠玑上所言，那就是 psuedo code: select =m; remaining =n; for i=[0..n] if(b... [阅读全文]

# stdio.h void adjust( *list,const root,const n); void HeapSort( *list,const n) { i=0; for(i=n/2;i=1;i--) adjust(list,i-1,n); t=list[n]; list[n]=list[0]; list[0]=t; (n1) HeapSor... [阅读全文]

堆排序在最坏情况下其时间复杂度也能达到O(nlogn)相对于快速排序来说这是它最大优点此外堆排序仅需要个记录大小供交换用辅助存储空间堆排序数据结构是 2叉堆 2叉堆特点有两个个是它是棵完全 2叉树另个是它根结点小于孩子结点所以我们很容易找到它最小结点----根结点；当然如果你想找到最大结点话那就要扫描所有叶子结点这是很费时间如果你想找是最大结点话你最好把它弄成个... [阅读全文]

# stdlib.h# stdio.h# time.h# MAX_LENGTH 100/*Show usage*/void usage(char * prog){ prf(\"%s Usage:\\n\", prog); prf(\"%s the count of numbers to sort (should be less than 100)\\n\", p... [阅读全文]