堆1中介绍了堆的定义性质以及建堆过程,这篇主要介绍堆排序以及堆的一种应用---优先级队列
1、堆排序
堆排序算法,先用build_max_heap将输入数组A[0,...,n-1]建立一个最大堆。因为数组中最大元素在A[0],则可以通过交换A[0]和A[n-1],此时将最大数A[n-1]存入结果数组result中,并将此节点去掉,此时数组就剩下A[0,...,n-2],由于互换,新的根元素可能违背了最大堆的性质,此时再调用建堆子程序Max_heapify(A,0)保持此性质,在A[0,...,n-2]中构造最大堆。不断递归这个过程,堆的大小从n-1降到1。c语言程序如下://堆排序
void heap_sort(int nums[],int len){
//首先建一个大根堆
build_max_heap(nums,len);
int *result = new int[len];//存放排好序的数组
for(int i=len-1;i>=1;i--){
*result++=nums[0];//最大数一直在根上,赋值 后,移除最大元素
nums[0]=nums[i];//从最后一个元素开始遍历,将其移到根部,并执行保持最大堆子程序,找到去除最大元素的次大元素,以此类推
max_heapify(nums,i,0);
}
*result=nums[0];
}
分析此算法:建堆运行时间O(n),循环n-1次,每次循环中执行O(log2^n)+c,因此总的运行时间为O(n)+(n-1)(O(log2^n)+c)=O(nlog2^n)
2、堆的一种应用---优先级队列
优先级队列是一种用来维护一组元素构成的集合S的数据结构,每一个元素有一个关键字key。分为最大优先级队列和最小优先级队列。一个最大优先级队列支持一下操作:
(1)maximum(S):返回S中最大关键字的元素
(2)extract_max(S):去掉并返回S中最大关键字的元素
(3)increase_key(S,x,k):将元素x的关键字的值增加到k,这里k值不能小于x的原关键字的值
(4)insert(S,x):将元素x插入集合S
最大优先级队列的一个应用是一台分时计算机上进行作业调度。队列对要执行的作业以及优先级进行记录并调度。当一个作业完成时或者中断时,可用extract_max操作从所有等待的作业中,选出一个优先级最高的作业来执行。
优先级队列可以用堆来实现。
几个操作实现如下:
//返回nums中具有最大关键字的元素
int maximum(int nums[],int len){
return nums[0];
}
//去掉,并返回nums中具有最大关键字的元素
int extract_max(int nums[],int len){
if(len<1){
cout<<"error:heap underflow"<<endl;
}
int max=nums[0];
nums[0]=nums[len-1];
nums[len-1]=NULL;
max_heapify2(nums,len-1,0);
return max;
}
//将nums[index]的关键字的值增加到key,增加后将其移到合适的位置,使其满足最大堆
void increase_key(int nums[],int len,int index,int key){
if(key<nums[index]){
cout<<"error:new key is smaller than current key"<<endl;
}
nums[index]=key;
int parent_index=(index-1)/2;
int temp=0;
while(index>=0&&nums[index]>nums[parent_index]){//类似插入排序
temp=nums[index];
nums[index]=nums[parent_index];
nums[parent_index]=temp;
index=parent_index;
parent_index=(index-1)/2;
}
}
//将x插入最大堆的适合位置,首先加入负无穷的叶子节点,然后调用increase_key()设置新节点的值并移到合适位置
void insert(int nums[],int len,int x){
int key=INT_MIN;
nums=(int *)realloc(nums,len+1);
nums[len]=key;
increase_key(nums,len+1,len,x);
}
分析四种操作:第一种操作:O(1)第2、3、4操作:O(log2^n)
分享到:
相关推荐
特殊的数据结构-堆.pptx
如题。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
比较详细地讲述了堆排序的思路和代码实现,适合初学者
本资源是博文【数据结构】有关堆你知多少?的配套演示资料,包含堆的结构、堆的调整算法、堆的两种应用的动画演示。可结合以下博文查看:http://t.csdn.cn/ahdIh
数据结构-快速和堆排序.ppt该文档详细且完整,值得借鉴下载使用,欢迎下载使用,有问题可以第一时间联系作者~
1.1 针对考研数据结构的代码书写规范以及C 与C 语言基础1 1.1.1 考研综合应用题中算法设计部分的代码书写规范1 1.1.2 考研中的C 与C 语言基础3 1.2 算法的时间复杂度与空间复杂度分析基础 12 1.2.1 考研中的算法时间...
《数据结构》严蔚敏版 堆排序
数据结构-3期(KC002) 堆排序算法.docx 学习资料 复习资料 教学资源
介绍数据结构堆(Heap)的概念、特点、优缺点、适用场景和Java示例代码
主要内容包括:算法效率的输入规模、阶和大O,数据结构的无序和有序列表,队列和栈基于数组和链表的设计实例,递归详解,二叉查找树和AVL树,堆、散列表和排序以及图论等。对于每一种数据结构的性质和用途,《计算机...
数据结构--内部排序算法 1、下列排序算法中,_____________排序在某趟结束后不一定能选出一个元素放到其最 终的位置上。 (1)选择 (2)冒泡 (3)归并 (4)堆 2、下列排序算法中,依次将待排序列中的元素和前面...
基本操作:针对每种数据结构,定义了一系列基本的操作,包括但不限于插入、删除、查找、更新、遍历等,并分析这些操作的时间复杂度和空间复杂度。 算法: 算法设计:研究如何将解决问题的步骤形式化为一系列指令,...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
Java语言编写的数据结构-排序。包括冒泡排序、选择排序、插入排序、希尔排序、快排、堆排序。
数据结构(C语言版) 第10章 排序 内 容 10.1 基本概念 10.2 冒泡排序 10.3 选择排序 10.4 插入排序 10.5 希尔排序 10.6 快速排序 10.7 堆排序 10.8 归并排序 10.9 基数排序
\数据结构flash演示\版本1\10-4-2堆排序大顶堆.swf \数据结构flash演示\版本1\10-4-3堆排序大顶堆.swf \数据结构flash演示\版本1\10-4-4堆排序建立堆.swf \数据结构flash演示\版本1\10-5-2归并排序.swf \数据...
算法与数据结构它们分别涵盖了以下主要内容: 数据结构(Data Structures): 逻辑结构:描述数据元素之间的逻辑关系,如线性结构(如数组、链表)、树形结构(如二叉树、堆、B树)、图结构(有向图、无向图等)...
这是我买的一本课程设计案例书上的源代码,上面的案例很经典,特别适合于作 毕业设计的学生使用,当然了,也可以做为做课程设计的学生以参考,希望能给 大家提供帮助!!
1、采用堆分配存储建立一个串,并实现串的赋值、比较、联结、求子串、求串的长度、串复制等基本操作。 2、串的模式匹配
这是一个利用堆分配方式实现串的基本操作的小程序,用C++ 写的,欢迎修改指正!