精选文章 堆排序(最大堆)

堆排序(最大堆)

作者:ouyangjun__ 时间: 2021-02-05 09:57:10
ouyangjun__ 2021-02-05 09:57:10
【摘要】一)定义和性质

定义:堆是按照完全二叉树的顺序结构存储在一个一维数组中,逻辑存储是完全二叉树,物理存储是数组。

性质:具有完全二叉树的顺序结构特性。

           对于任意的节点,从上往下,父节点都大于左孩子和右孩子。

           根节点最大的情况,称为最大堆。

 

用数组存储二叉堆,堆的顶点下标可以从0开始也可以从1开始。

堆顶下标从0开始:父节点=(i-1...

一)定义和性质

定义:堆是按照完全二叉树的顺序结构存储在一个一维数组中,逻辑存储是完全二叉树,物理存储是数组。

性质:具有完全二叉树的顺序结构特性。

对于任意的节点,从上往下,父节点都大于左孩子和右孩子。

根节点最大的情况,称为最大堆。

 

用数组存储二叉堆,堆的顶点下标可以从0开始也可以从1开始。

堆顶下标从0开始:父节点=(i-1)/2、左子节点=2*i+1、右子节点=2*i+2,根节点等于0

堆顶下标从1开始:父节点=i/2、左子节点=2*i、右子节点=2*i+1,根节点等于1

 

调整原理:围绕最后一个叶子节点开始调整,也就是从33开始调整。

源数据图形:

堆排序(最大堆)1

最大堆图形:

堆排序(最大堆)2

二)排序源码

1、初始化

import java.util.Arrays;

/**
 * 堆排序(最大堆)
 * 计算方式: 父节点为(i-1)/2
 * 左子节点为2*i+1
 * 右子节点为2*i+2
 * @author ouyangjun
 */
public class MaxHeap { private int[] elementData; private int size; private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 默认初始容量 public MaxHeap() { this(8); } // 指定初始容量 public MaxHeap(int initialCapacity) { if (initialCapacity > 0) { elementData = new int[initialCapacity]; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 扩容 * @param minCapacity */ private void grow(int minCapacity) { if (minCapacity - elementData.length > 0) { int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) { newCapacity = minCapacity; } if (newCapacity - MAX_ARRAY_SIZE > 0) { if (minCapacity < 0) { throw new OutOfMemoryError(); } newCapacity = minCapacity > MAX_ARRAY_SIZE ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } elementData = Arrays.copyOf(elementData, newCapacity); } } // 父节点 private int parent(int n) { return (n-1)/2; } // 左子节点 private int left(int n) { return 2 * n + 1; } // 右子节点 private int right(int n) { return 2 * n + 2; }

}

2、调整最大堆

/**
  * 向上调整为最大堆, 向上调整只需要考虑双亲结点
  * @param array
  */
private void upMaxHeap(int[] array, int length) { // 找到最后一个叶子节点的父节点 int parentIndex = parent(length); for (int i = parentIndex; i >= 0; i--) { upMaxHeap(array, i, length); }
}
	
private void upMaxHeap(int[] array, int index, int length) { // 先把第一个左孩子作为最大值 int max = left(index); while (max < length) { if (max + 1 < length && array[max + 1] > array[max]) { max += 1; } if (array[index] >= array[max]) { break; } int t = array[max]; array[max] = array[index]; array[index] = t; index = max; max = left(index); }
}

3、添加

// 添加
public void add(int value) { // 判断是否需要扩容 grow(size + 1); // 插入元素 elementData[size++] = value; // 调整成最大堆 upMaxHeap(elementData, size);
}

// 打印
public void print() { System.out.print("["); for (int i = 0; i < size; i++) { System.out.print(elementData[i] + ", "); } System.out.print("]");
}

4、main方法测试

public static void main(String[] args) { MaxHeap heap = new MaxHeap(); heap.add(14); heap.add(56); heap.add(55); heap.add(45); heap.add(11); heap.add(3); heap.add(21); heap.add(76); heap.add(23); heap.add(34); heap.add(43); heap.add(33); // 打印 heap.print(); }

 

识别二维码关注个人微信公众号

堆排序(最大堆)3

本章完结,待续,欢迎转载!
 
本文说明:该文章属于原创,如需转载,请标明文章转载来源!

勿删,copyright占位
分享文章到微博
分享文章到朋友圈

上一篇:堆排序(最小堆)

下一篇:va_list函数

您可能感兴趣

  • VCL中的堆与栈

    栈(stack)与堆(heap)是C|C++中常见的概念,要想学好C|C++,我们也必须了解这两个概念的区别与联系。但BCB中的VCL是用object pascal语言写的,她具有object pascal的很多特性,这要我们在使用时注意,下面就我在这方面的学习感受写点观点供朋友们参考。     栈是存放函数的所有动态局部变量及函数调用和返回的有关信息的一块内存。栈的内存管理严格遵循先进后出...

  • 数据结构与算法(C#实现)系列---二叉堆(数组实现)

    数据结构与算法(C#实现)系列---二叉堆(数组实现) using System; using System.Collections;   namespace DataStructure {      ///      /// BinaryHeap 的摘要说明。-------二叉堆(基于数组的实现)      ///      public class BinaryHeap:IPrior...

  • 方博士的讲座上的最大收获

    昨天和方博士咨询了一下,INTEL的美国研发学院里,如何做代码控制的。答案和我预期的太不一样了。研究院里,代码的控制主要是CVS,其次是PERFORCE。代码管理是个很复杂的系统,变更也是在所难免的。在权限控制方面,不像国内的某些公司那么严格,代码是可以代回家继续研究的,不受限制,除非是芯片的图纸,这是严格保密的,所有研发人员的智慧结晶。另外,更重要的是,所有人都很遵守职业道德,没有人把代码...

  • 最大在线人数统计

    global.asax:          protected   void  Session_Start(Object sender, EventArgs e)          {                 Application.Lock();             DataSet objDataSet=new DataSet()             objDataSet...

  • [翻译]关于堆和堆栈

    对于堆(heap)和堆栈(stack),尽管说过很多次,不过一直都不是很清楚。个人认为这篇帖子说的还是比较好懂的,便翻译了过来。有些地方可能不太准确,因此后面附上了原文。堆栈用于存储临时值。当你调用一个函数时,n字节被分配到堆栈的顶层,其中n是所有局部变量的字节之和。一个用于标记自身的特殊函数所占用的区域,我们称之为堆栈帧。由于每个函数都可以调用其他函数,因此最终将会得到一连串的堆栈帧,每一...

  • 最大可用性保护模式dataguard实施

    可能看着有点儿乱,基本思路是利用控制文件复制一个库到灾备机,然后配置dataguard,最后由最大性能升级到最大可用性。 [@more@] 环境描述 A机:primary(这里A机在现场为HA的主,对于主的所有参数调整都要对备作相应调整)192.168.1.4 B机:standby(这里指现场的灾备机)192.168.1.7 Oracle_SID是testdb。 环境:aix ,...

  • MAPI Session 超出最大连接数

    Q: 您好: MAPI SESSION超出默认值之后,就会阻止MAPI客户端的连接。默认是32个session,如果超出就会报错。 ID:9646 Mapi 会话“/o=mail/ou=First Administrative Group/cn=Recipients/cn=songx”超出了 40 个“session”类型的对象的最大限制。 我对MAPI SEESION的理解如下: c...

  • 按某一字段分组取最大(小)值所在行的数据

    -- 按某一字段分组取最大(小)值所在行的数据 (爱新觉罗.毓华  2007 - 10 - 23于浙江杭州) /**/ /*数据如下:name val memoa    2   a2(a的第二个值)a    1   a1--a的第一个值a    3   a3:a的第三个值b    1   b1--b的第一个值b    3   b3:b的第三个值b  ...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。

华为云40多款云服务产品0元试用活动

免费套餐,马上领取!
堆排序(最大堆)介绍:华为云为您免费提供堆排序(最大堆)在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多堆排序(最大堆)的相关内容。| 移动地址: 堆排序(最大堆) | 写博客