网站首页 / 育儿 / 正文

堆排序代码解析(堆排序的算法及代码实现)

时间:2022-04-14 11:35:12 浏览:6984次 作者:用户投稿 【我要投诉/侵权/举报 删除信息】

多条告白如次剧本只需引入一次

暂时这个系列的作品都挑着特殊典范的,让人暂时一亮的算法,即日的堆排序算法即是个中一个。 开始领会什么是堆,这内里堆(Heap)并不是步调中外存地区,而是一种实足二叉树表白的数据构造。 堆具备以次特性

是一个实足二叉树堆的每个节点的值必需大于即是安排树节点(大顶堆),或小于即是安排树节点(小顶堆)。大略证明下,实足二叉树是除去结果一层叶子节点外,其余的节点都有两个子树,而叶子节点不妨没有子树,大概惟有左子树。 如次图即是个大顶堆:

小顶堆

堆保存

堆由于是实足二叉树,特殊符合用数组保存,上海图书馆为大顶堆的保存情景,个中a[0]不必, a[1]为大顶堆的极点,也即是最大的数据,a[12]= 7 为左子树极点,a[12+1]= 6为右子树的极点,其余节点情景顺序类比。

堆的两种操纵

向堆插入元素

用图来表白如次:

向堆插入元素,先插入到结果一个数组元素场所,而后和本人的父节点6比拟,因为比6大不满意大顶堆的前提,以是9和6调换,而后9再和堆顶元素8比拟,又不满意大顶堆前提,连接调换,结果产生一个大顶堆,这个办法叫堆化。

简略堆顶元素

对于大顶堆来说,堆顶的元素为最大值,顺序简略堆顶元素并输入,那么即是将数字从大向小陈设了。

这内里又个本领,即是简略堆顶元素的功夫,不许径直简略,要用堆顶元素和结果一个元素做调换,而后按照堆的特性安排堆,直到满意前提。

完备代码如次:

package com.dianneng.lms;public class TestHeap { private int [] a; private int n; private int count; public TestHeap(int cap) { a = new int[cap+1]; n = cap; count = 0; } public void swap(int i,int j) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; return; } public void print(){ for (int i = 0; i <= count;i++) { System.out.print(a[i]+"t"); } } public int insert( int v) { if (count == n) { System.out.println("Heap is full!"); return -1; }else { a[++count] = v; int i = count; while (i/2 >0 && a[i] > a[i/2]) { swap(i,i/2); i = i/2; } } return 0; } public int removeMax() { if (count == 0) { return -1; } System.out.print(a[1]+"t"); a[1] = a[count]; --count; heapify(count,1); return 0; } private void heapify(int n, int i) { while(true) { int maxPos = i; //经过安排子树极点比拟赢得最大数节点 if (i*2 <= n && a[i] <a[i*2] ){ maxPos = i*2; } if (i*2+1 <= n && a[maxPos] < a[i*2+1]) { maxPos = i*2+1; } //仍旧是最大的不必调换了 if (maxPos == i) { break; } //须要调换 swap(i,maxPos); //i指向待调换的 i = maxPos; } } public static void main(String [] args) { TestHeap th = new TestHeap(18); th.insert(8); th.insert(7); th.insert(6); th.insert(5); th.insert(4); th.insert(3); th.print(

版权声明:
本文内容由互联网用户自发贡献,该文观点仅代表作者本人,因此内容不代表本站观点、本站不对文章中的任何观点负责,内容版权归原作者所有、内容只用于提供信息阅读,无任何商业用途。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站(文章、内容、图片、音频、视频)有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至353049283@qq.com举报,一经查实,本站将立刻删除、维护您的正当权益。