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

堆排序(最大堆)

作者:ouyangjun__ 时间: 2019-11-03 09:15:15
ouyangjun__ 2019-11-03 09:15:15

一)定义和性质

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

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

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

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

 

用数组存储二叉堆,堆的顶点下标可以从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函数

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

您可能感兴趣

  • 功能fine秒mine!苹果“偷走”了安卓系统,但它表现得更好

    全文共1670字,预计学习时长5分钟 图源:unsplash 不久前的开发者大会上,苹果发布了iOS 14,展示了一些将在今年晚些时候出现在iPhone上的重要功能,比如允许用户将应用程序中的内容导入主屏幕的小部件,以及画中画视频功能。 安卓迷们发现了一些很明显的事情:许多在年度开发者大会上发布的功能已经在安卓上使用了很多年了。没错,小部件从一开始就是安卓系统的一部分,它可以让用户在主屏幕上...

  • 字节跳动三面拿offer:网络+IO+redis+JVM+GC+红黑树+数据结构

    5G的到来证明了互联网行业发展一如既往的快,作为一名开发人员(Java岗)梦想自然是互联网行业的大厂,这次有幸获得面试字节跳动的机会,为此我也做出了准备在面试前一个月就开始做准备了,也很荣幸的拿到了字节跳动的offer,这里分享一份字节跳动三面过程! 字节一面: hashmap,怎么扩容,怎么处理数据冲突?怎么高效率的实现数据迁移? Linux的共享内存如何实现,大概说了一下。 socket...

  • grafana使用MYSQL数据源展示

    新增数据源 Grafana支持许多不同的数据源。每个数据源都有一个特定的查询编辑器,该编辑器定制的特性和功能是公开的特定数据来源。 官方支持以下数据源:Graphite,InfluxDB,OpenTSDB,Prometheus,Elasticsearch,CloudWatch和KairosDB。 每个数据源的查询语言和能力都是不同的。 你可以把来自多个数据源的数据组合到一个仪表板dashbo...

  • HDFS的功能和架构原理详解

    目录 一、分布式文件系统的理解 二、HDFS的架构详细剖析 1. 文件分块存储&3副本 2. 抽象成数据块的好处 3. HDFS架构 4. 扩展 三、HDFS的shell命令操作 四、HDFS安全模式 一、分布式文件系统的理解 最直观的理解便是三个臭皮匠,顶个诸葛亮。 很多的磁盘加一起就可以装下天下所有的avi 类似于你出五毛,我出五毛,我们一起凑一块的效果 如下图: 二、HDFS的架构详细...

  • 网络七层协议 OSI开放式互联参考模型

    解决两台物理机之间的通信需求:机器A往机器B发送比特流,机器B能收到这些比特流,这就是物理层要做的事情。物理层主要定义了物理设备的标准,如网线的类型,光纤的接口类型,各种传输介质的传输速率等。它的主要作用是传输比特流,将0101数据转换为电流强弱来进行传输,到达目的机器后再转换为0101的机器码,即数模转换与模数转换。这一层的数据叫做比特,网卡就是工作在这一层的。 在传输比特流的时候,会产生...

  • Linux系统内存

    Linux 内存是后台开发人员,需要深入了解的计算机资源。合理的使用内存,有助于提升机器的性能和稳定性。本文主要介绍Linux 内存组织结构和页面布局,内存碎片产生原因和优化算法,Linux 内核几种内存管理的方法,内存使用场景以及内存使用的那些坑。 从内存的原理和结构,到内存的算法优化,再到使用场景,去探寻内存管理的机制和奥秘。 一、走进Linux 内存 1、内存是什么? 1)内存又称主存...

  • kubernetes使用组件具体介绍

    1. kubernetes介绍 1.1. kubernetes介绍 kubernetes是一种开源的容器编排工具,通过调度系统维持用户预期数量和状态的容器正常运行。kubernetes提供的功能: 服务发现和负载均衡:Kubernetes 可以使用 DNS 名称或自己的 IP 地址公开容器,如果到容器的流量很大,Kubernetes 可以负载均衡并分配网络流量,从而使部署稳定。 存储编排 K...

  • K8s CNI网络最强对比:Flannel、Calico、Canal和W

    介 绍 网络架构是Kubernetes中较为复杂、让很多用户头疼的方面之一。Kubernetes网络模型本身对某些特定的网络功能有一定要求,但在实现方面也具有一定的灵活性。因此,业界已有不少不同的网络方案,来满足特定的环境和要求。 CNI意为容器网络接口,它是一种标准的设计,为了让用户在容器创建或销毁时都能够更容易地配置容器网络。在本文中,我们将集中探索与对比目前最流行的CNI插件:Flan...

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

免费套餐,马上领取!
CSDN

CSDN

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