1、堆数据结构是一种数组对象。
2、该数组对象的两个属性:
length【A】数组元素的个数
heap-size【A】存放在A中的堆的元素个数
3、父节点与其左右子节点的关系:
父节点:parent(i)
return i/2;
左子节点:getLeftChild(i)
return 2*i+1;
右子节点:getRightChild(i)
return 2*i+2;
4、最大堆的特性:(堆排序)
A[PARENT(i)]>=A[i];
最小堆的特性:(优先队列)
A[PARENT(i)]<=A[i];
5、堆排序:
1.建堆:
Build_heap(A)
heap_size(A)<--length[A]
for i<--取整[length[A]/2]-1
do Max_heapify(A,i)
2.调整堆:
Max_heapify(A,i)
left<-getLeftChild(i)
right<-getRightChild(i)
if left<=heap_size[A]&&A[left]>A[i]
then largst<-left
else largst<-i
if right<=heap_size[A]&&A[right]>A[i]
then largst<-right
if largst != i
then exchange A[i]<-->A[largst]
Max_heapify(A,largst)
3.堆排序:
HeapSort(A)
Build_heap(A)
for i<--length[A]-1
do exchange A[0]<---heap_size[A]-1
Max_heapify(A,i)
6、Java代码实现:
public class HeapSort
{
/**
* 堆排序的方法
* @param array
*/
public static void heapSort(int a[],int alen)
{
int hlen=alen;
int temp;
//1、建堆
BuildHeap(a,hlen);
for(int i=alen-1;i>=0;i--)
{
temp=a[0];//将数组的最后一个元素与第一个元素交换
a[0]=a[i];
a[i]=temp;
hlen--; //堆长度减1
Max_HeapIFY(a,hlen,0);//调整堆
}
}
/**
* 建堆的方法
*/
public static void BuildHeap(int a[],int hlen)
{
int begin=hlen/2-1;
for(int i=begin;i>=0;i--)
{
Max_HeapIFY(a,hlen,i);
}
}
/**
* 调整堆的方法
*/
public static void Max_HeapIFY(int a[],int hlen,int i)
{
int left=getLeftChild(i);
int right=getRightChild(i);
int largst =i;
int temp;
if(left<hlen&&a[largst]<a[left])
{
largst=left;
}
if(right<hlen&&a[largst]<a[right])
{
largst=right;
}
if(i!=largst)
{
temp=a[largst]; //将值最大的数与当前数交换
a[largst]=a[i];
a[i]=temp;
//在获取当前的左右孩子节点
Max_HeapIFY(a,hlen,largst);
}
}
/**
* 获取左孩子节点
*/
public static int getLeftChild(int i)
{
return 2*i+1;
}
public static int getRightChild(int i)
{
return 2*i+2;
}
public static void main(String[] args)
{
int a[]={16,4,10,14,7,9,3,2,8,5,1,5,33,45,323,2323,876};
int alen=a.length;
//未排序的顺序
System.out.println("未排序时,数组元素的顺序:");
for(int i=0;i<alen;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
System.out.println("排序后,数组元素的顺序:");
heapSort(a,alen);
//排序后的顺序
for(int i=0;i<alen;i++)
{
System.out.print(a[i]+" ");
}
System.out.println();
System.out.println("数组中最大的十个数为:");
for(int i=alen-1;i>=alen-10;i--)
{
System.out.print(a[i]+" ");
}
}
}
分享到:
相关推荐
idea项目:一个主类选择调用6个排序类,记录了学习排序算法的过程,可以自己更改优化,每一种排序是一个类,有需要可以copy走,可重用性强
堆排序6.py 使用python实现堆排序6.py 使用python实现堆排序6.py 使用python实现堆排序6.py 使用python实现堆排序6.py 使用python实现堆排序6.py 使用python实现堆排序6.py 使用python实现堆排序6.py 使用python实现...
1.基本思想 2.排序过程 3.代码实现 4.如何优化 5.复杂度 6.使用场景 1.基本思想 2.排序过程 1.先将初始文件R[1..n]建成一个大根堆,此堆
第1章 Windows应用程序开发入门..........................................................................................16 1.1 第一个实例程序...............................................................
排序—6.堆排序(*)(P217);排序—6.堆排序;排序—6.堆排序;51;;;;38;排序—6.堆排序;几种排序的比较;巩固练习;3. 若一组记录的排序码为(46,79,56,38,40,84),则利用快速排序的方法,以第一个记录为基准得到...
基于sudo 1.9.5p2源码编译打包,用以解决Sudo 堆溢出(CVE-2021-3156)漏洞,已再rhel6.5及centos6.5上安装验证,直接使用rpm -Uvh升级安装即可
RX厂房+6.450M堆外核测导向及通风组件安装施工方案
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS 共...
ACM 程序设计:堆及左偏树-p6.pdf
31 6. const char*, char const*, char*const的区别 ..................................................................................... 32 7. C中可变参数函数实现 .........................................
1.4 堆迭的照片拼贴画 1.5 创建移轴玩具模型效果 第2章 影室效果 2.1 高科技的动感产品构建 2.2 给照片添加纹理和陈旧效果 2.3 高对比度砂质肖像效果 第3章 商业特效 3.1 高科技运动效果的个人简历页面 3.2 线束背景...
交换机DEBUG信息开关.............................................................................................................6 交换机SNMP配置 ..........................................................
1.2.3算法的时间复杂度................................................................................................6 1.3 数学预备知识....................................................................
26红黑树 27红黑树_0 28红黑树_1 29红黑树_2 30红黑树_3 31红黑树_4 32红黑树_5 33红黑树_6 34堆 35堆排序 36哈希与映射的概述 37B树有什么用 38B树的概念 39图_邻接矩阵 40图_邻接表 41图_DFS 42图_BFS 共...
第2章至第6章分别讨论了线性表、栈和队列、串和数组、树型结构和图结构等常用的数据结构及其应用,以及在.NET框架中相应的数据结构;第7、8两章分别讨论了排序和查找常用的各种方法及其应用以及在.NET框架中相应的...
1.直接插入排序--增量法 2.希尔排序 3.交换排序 4.快速排序 5.直接选择排序 6.堆排序 7.归并排序
一文带你了解JavaScript垃圾回收机制 目录 1. 概述 2. 内存管理 3. 垃圾回收 4. GC算法介绍 5. 引用计数算法 ...5. 堆快照查找分离DOM 6. 判断是否存在频繁GC 总结 1. 概述 2. 内存管理 3.
排序实现。1.冒泡排序,2.选择排序,3.插入排序,4.归并排序,5.希尔排序,6.堆排序,7.快速排序
Athena_6_layer-堆疊表.是6层板的一个常用叠层结构,方便大家参考与使用
6. 堆料,去料,擦除,磨光等操作模拟现实雕塑过程,简单直观。 7. 颜色模板,限高保低,高度模式,擦除,取消/重做等辅助工具,使得虚拟雕塑在某些方面高于现实雕塑。 8. 灵活的浮雕生成方式(区域浮雕/单线浮雕/...