前序:
(二叉)堆数据结构是一种数组对象,它可以被视为一棵完全二叉树。树中每个节点与数组中存放该节点值的那个元素对应。
树的每一层都是填满的,最后一层除外。
树的根为a[1] (在这里是从1开始的,也可以从0开始),给定了某个节点的下标i,其父节点为i/2,左二子为2*i,右儿子为2*i+1。
二叉堆满足二个特性:
1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。
2.每个结点的左子树和右子树都是一个二叉堆(最大堆或最小堆)。
当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。
当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。
保持堆的性质:
MaxHeap是对最大堆进行操作的最重要的子程序。
以i为根的子树:
在算法每一步中,从a[i], a[Left(i)], a[Right(i)]找出最大值,并将其下标存在LargestIndex中。如果a[i]是最大的,则以i为根的子树已是最大堆,程序结束。
否则i的某个子结点中有最大元素则交换a[i],a[LargetIndex],从而使i及子女满足堆性质。下标为LargestIndex的结点在交换后的值为a[i],以该结点为根的子树又有可能违反最大堆的性质,因而又要对该子树递归调用MaxHeap,重新使子树平衡。
-
-
-
intMaxHeap(inta[],intindex,intn){
-
intLargestIndex=index;
-
-
intLeftIndex=2*index;
-
-
intRightIndex=2*index+1;
-
if(LeftIndex<=n&&a[LeftIndex]>a[LargestIndex]){
-
LargestIndex=LeftIndex;
-
}
-
if(RightIndex<=n&&a[RightIndex]>a[LargestIndex]){
-
LargestIndex=RightIndex;
-
}
-
-
-
inttemp;
-
if(LargestIndex!=index){
-
-
temp=a[index];
-
a[index]=a[LargestIndex];
-
a[LargestIndex]=temp;
-
-
MaxHeap(a,LargestIndex,n);
-
}
-
return0;
-
}
建堆:
我们可以自底向上的用MaxHeap来将一个数组a[1-n]变成一个最大堆,子数组a[n/2+1,........n]中的元素是树中的叶子,因此每个都可以看做只含一个元素的堆,满足最大堆的要求,不用调整。所以只需调整以a[n/2........1]中元素为根的子树使之成为最大堆。
-
-
intBuildMaxHeap(inta[],intn){
-
inti;
-
-
for(i=n/2;i>=1;i--){
-
-
MaxHeap(a,i,n);
-
}
-
return0;
-
}
a数组
初始堆:自底向上从最后一个非叶节点开始调整:
(a) (b)
(c) (d)
每次调整都是从父节点、左孩子节点、右孩子节点三者中选择最大者跟父节点进行交换(交换之后可能造成被交换的孩子节点不满足堆的性质,因此每次交换之后要重新对被交换的孩子节点进行调整)。
堆排序:
开始时,堆排序先用BuildMaxHeap将输入数组a[1-n]构造成一个最大堆。又因为数组中最大元素在根a[1],则可以通过它与a[n]交换来达到最终的正确位置。现在,如果从堆中”去掉“结点n(不是真的删除,而是通过修改堆的元素个数n),可以很容易的将a[1-(n-1)]建成最大堆。原来根的子女依旧是最大堆,二新交换的根元素很有可能违背最大堆的性质。这时调用MaxHeap重新调整一下。在a[1-(n-1)]中构造出最大堆。堆排序不断重复这一过程,堆的大小由n-1一直降到2.从而完成排序的功能
-
-
intHeapSort(inta[],intn){
-
inttemp;
-
-
BuildMaxHeap(a,n);
-
-
for(inti=n;i>=2;i--){
-
-
temp=a[i];
-
a[i]=a[1];
-
a[1]=temp;
-
-
n--;
-
-
MaxHeap(a,1,n);
-
}
-
return0;
-
}
(a) (b)
(c) (d)
(e) (f)
(g)
(h) (i)
(j) (k)
红色为排序后的结果;
代码:
-
#include<stdio.h>
-
#include<stdlib.h>
-
-
-
intMaxHeap(inta[],intindex,intn){
-
intLargestIndex=index;
-
-
intLeftIndex=2*index;
-
-
intRightIndex=2*index+1;
-
if(LeftIndex<=n&&a[LeftIndex]>a[LargestIndex]){
-
LargestIndex=LeftIndex;
-
}
-
if(RightIndex<=n&&a[RightIndex]>a[LargestIndex]){
-
LargestIndex=RightIndex;
-
}
-
-
-
inttemp;
-
if(LargestIndex!=index){
-
-
temp=a[index];
-
a[index]=a[LargestIndex];
-
a[LargestIndex]=temp;
-
-
MaxHeap(a,LargestIndex,n);
-
}
-
return0;
-
}
-
-
-
-
intBuildMaxHeap(inta[],intn){
-
inti;
-
-
for(i=n/2;i>=1;i--){
-
-
MaxHeap(a,i,n);
-
}
-
return0;
-
}
-
-
-
intHeapSort(inta[],intn){
-
inttemp;
-
-
BuildMaxHeap(a,n);
-
-
for(inti=n;i>=2;i--){
-
-
temp=a[i];
-
a[i]=a[1];
-
a[1]=temp;
-
-
n--;
-
-
MaxHeap(a,1,n);
-
}
-
return0;
-
}
-
intmain(){
-
intn=6;
-
-
inta[]={0,3,17,8,7,16,20};
-
HeapSort(a,n);
-
for(inti=1;i<=n;i++){
-
printf("%d",a[i]);
-
}
-
return0;
-
}
-
分享到:
相关推荐
本书是Sedgewick彻底修订和重写的C算法系列的第一本。全书分为四部分,共16章。第一部分“基础知识”(第1—2章)介绍基本算法分析原理。第二部分“数据结构”(第3~5章)讲解算法分析中必须掌握的数据结构知识,...
堆排序 定理 比较排序的算法速度不会超过nlgn 决策树 举例3个数进行比较排序的决策树 每一个内部节点都会有一个下标为i:j标记,左孩子为小于等于,右孩子为大于 每一个叶结点表示一个排序结果,其中有一个是正确的...
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
九、图像特征提取与匹配之SIFT算法 (SIFT算法系列五篇文章) 九(续)、sift算法的编译与实现 九(再续)、教你一步一步用c语言实现sift算法、上 九(再续)、教你一步一步用c语言实现sift算法、下 九(三续):...
《Reilly精品图书系列·算法精解:C语言描述》内容包括: · 数据结构和算法的概念,以及使用它们的原因和意义 · 指针和递归 · 算法分析 · 常用数据结构:链表、栈、队列、集合、哈希表、树、堆、...
本书是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还...
每一章的末尾都会有一系列问题和对应的回答,旨在强调这一章的重要思想…… 本书中的代码尤为值得强调:所有实现都采用C语言编写,所有代码都优先用于教学目的,所有代码都在4种平台上经过完整测试,头文件记录了...
本书是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还...
每一章的末尾都会有一系列问题和对应的回答,旨在强调这一章的重要思想……《算法精解:C语言描述》中的代码尤为值得强调:所有实现都采用C语言编写,所有代码都优先用于教学目的,所有代码都在4种平台上经过完整测试...
算法分类:排序算法(如冒泡排序、快速排序、归并排序),查找算法(如顺序查找、二分查找、哈希查找),图论算法(如Dijkstra最短路径算法、Floyd-Warshall算法、Prim最小生成树算法),动态规划,贪心算法,回溯法...
本书是数据结构和算法领域的经典之作,十余年来,畅销不衰!全书共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法中最常用的技术——指针和递归,最后还...
他是我国计算机普及和高校计算机基础教育开拓者之一,现任全国高等院校计算机基础教育研究会会长、教育部全国计算机应用技术证书考试委员会主任委员。 谭浩强教授创造了3个世界纪录:(1)20年来他(及和他人合作)...
他是我国计算机普及和高校计算机基础教育开拓者之一,现任全国高等院校计算机基础教育研究会会长、教育部全国计算机应用技术证书考试委员会主任委员。 谭浩强教授创造了3个世界纪录:(1)20年来他(及和他人合作)...
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!《算法精解:C语言描述》共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法...
《算法精解:C语言描述》是数据结构和算法领域的经典之作,十余年来,畅销不衰!《算法精解:C语言描述》共分为三部分:第一部分首先介绍了数据结构和算法的概念,以及使用它们的原因和意义,然后讲解了数据结构和算法...
安琪拉教鲁班学算法之堆排序 《安琪拉教妲己学分布式》系列文章 安琪拉教妲己分布式限流 《安琪拉教百里守约学并发编程》系列文章 安琪拉教百里守约学并发编程之多线程基础 本文是来自读者群里@凯的建议,决定开一个...
最新Python3.5零基础+高级+完整项目(28周全)培训视频学习资料;本资料仅用于学习。 【课程内容】 第1周 开课介绍 python发展介绍 ...堆排序复习 归并排序 希尔排序 算法练习 栈和队列 数据结构其他