建立大根堆,处于堆顶的元素heap[0],则是最大的数,将这个heap[0]与最后一个元素交换,即与heap[n-1],交换,则最大的数被到了最后,再对heap[0]与heap[n-2]这些数根据大根堆调整,这些最大数又被调整到了heap[0],再将heap[0]与heap[n-2]对换,对heap[0]与heap[n-3大根堆调整
typedef struct minHeapMax{
int heap[40];
int currentSize;
};
//i是调节第几个关键字,m是堆的大小
void siftDownMax(minHeapMax &H ,int i,int m){
int j=0;
int temp = H.heap[i];
H.currentSize = m;
j = 2*i+1;
while(j<m){
if(j<m-1&&H.heap[j]<H.heap[j+1])
j = j+1;
if(temp<H.heap[j]){
H.heap[i] = H.heap[j];
i = j;
j = 2*j+1;
}else
break;
}
H.heap[i] = temp;
}
void createBigHeap(minHeapMax &H,int A[],int n){
int i=0;
H.currentSize = n;
for(i=0;i<n;i++){
H.heap[i] = A[i];
}
int currentPos = (H.currentSize-1)/2;
while(currentPos>=0){
siftDownMax(H,currentPos,H.currentSize);
currentPos--;
}
}
void main(){
minHeapMax H;
int temp;
int i=0;
int A[8] = {49,38,65,97,76,13,27,49};
createBigHeap(H,A,8);
for(i=0;i<8;i++){
printf("%d \n " ,H.heap[i]);
}
while(H.currentSize>0){
temp = H.heap[H.currentSize-1];
H.heap[H.currentSize-1] = H.heap[0];
H.heap[0] = temp;
H.currentSize--;
siftDownMax( H ,0, H.currentSize);
}
for(i=0;i<8;i++){
printf("%d \n " ,H.heap[i]);
}
}
分享到:
相关推荐
小菜初来乍到,水平有限,但个人觉得代码应该正确易懂吧,求网友指教
大根堆,小根堆,优先队列,堆排序,模版。
(1)用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区 ② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R...
基于c++实现以数组为基础大根堆和小根堆
堆排序算法的java实现,采用大根堆。时间复杂度为O(nlogn).
堆排序 在C#中实现堆排序,我们可以按照以下步骤编写代码: 建立大根堆:首先,从最后一个非叶子节点开始(即最后一个元素的父节点),逐个将它们调整为大根堆。大根堆的性质是每个节点的值都大于或等于其子节点的...
主要介绍了Java实现堆排序(大根堆)的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
用函数实现堆排序,并输出每趟排序的结果 Input 第一行:键盘输入待排序关键的个数n 第二行:输入n个待排序关键字,用空格分隔数据 Output 第一行:初始建堆后的结果 其后各行输出交换堆顶元素并调整堆的...
代码十分清楚的描述了堆排序是如何进行的,配合笔者写的博客,可以将此种算法掌握的十分牢靠,代码结构清晰。
c语言实现堆排序。代码实现的是建立大根堆
堆排序分为两个过程: 1.建堆。 堆实质上是完全二叉树,必须满足:树中任一非叶子结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 堆分为:大根堆和小根堆,升序排序采用大根堆,降序排序采用...
1.基本思想 2.排序过程 3.代码实现 4.如何优化 5.复杂度 6.使用场景 1.基本思想 2.排序过程 1.先将初始文件R[1..n]建成一个大根堆,此堆
本文实例为大家分享了C#实现堆排序的具体代码,供大家参考,具体内容如下 代码: /// /// 堆排序方法。... // 建立大根堆。 Console.WriteLine(Build max heap:); foreach (int i in a) { Console.Write
将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。 完全二叉树 说到堆排序,就不能不提完全二叉树,这些基本概念在网上到处都是,我摘了个最简单的。。 完全二叉树:除最后一层外,每一层上...
Java大根堆演示代码 在控制台输入java -jar maxHeap.jar后即可运行项目。 所支持的操作: 0:初始化一个新堆 1:向堆中插入一个数值 2:增大堆中某个节点的值 :堆排序操作 4:打印堆的树结构 5:打印堆排序结果 6:...
是关于数据结构中内部排序重要的排序的一些扼要说明 可以自己慢慢研究 是我们老师的课件
│ │ ├── HeapSort.php 堆排序 大根堆 │ │ ├── MBaseSort.php 基数排序 MSD │ │ ├── LBaseSort.php 基数排序 LSD │ │ ├── QuickSort.php 快速排序 │ ...
│ │ ├── HeapSort.php 堆排序 大根堆 │ │ ├── MBaseSort.php 基数排序 MSD │ │ ├── LBaseSort.php 基数排序 LSD │ │ ├── ShuttleSort.php 飞梭排序 │ ...
根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。二叉堆还常用于排序(堆排序)。 如下:最小堆(任意节点的优先级不小于它的子节点) 看看PHP SplHeap的实现: 显然它是一个抽象类,最大堆...