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

堆排序(最大堆)

作者: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占位
您找到想要的结果了吗?
堆排序(最大堆)
提交成功!非常感谢您的反馈,我们会继续努力做到更好
分享文章到微博
分享文章到朋友圈

上一篇:一文看懂用Python读取Excel数据

下一篇:va_list函数

您可能感兴趣

  • HDU 1506 Largest Rectangle in a Histogram(最大长方形)

    题目链接:Click here~~ 题意: 这就是前几篇已经提到的求最大长方形那道题。 解题思路: 如果每次都向前向后扫描,有时会重复扫描多次,导致超时。 我们可以用一个单调栈 (类似单调队列) 由低到高来存储它的高度,并用数组对每个高度记录一下它前面(包括它自己)一共有多少个比它高的,可以看做它的左宽。 按顺序考虑每个高度...

  • js + leetcode刷题:No.53 最大子序和

    题目: (面试题42. 连续子数组的最大和;面试题 16.17. 连续数列 均为改题,要求不同解法) 给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。 示例:...

  • week-5-A最大矩形(单调栈)

    题意 给一个直方图,求直方图中的最大矩形的面积。例如,下面这个图片中直方图的高度从左到右分别是2, 1, 4, 5, 1, 3, 3, 他们的宽都是1,其中最大的矩形是阴影部分。 输入格式说明:输入包含多组...

  • 【求区间最大最小值】Balanced Lineup POJ - 3264

    Balanced Lineup POJ - 3264 For the daily milking, Farmer John's N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ult...

  • 最大连续子序列和

    问题描述 给定一个数列,其中可能有正数也可能有负数,找出其中连续的一个子数列(不允许空序列),使它们的和尽可能大 解题思路 状态转移方程:sum[i] = max{sum[i-1]+a[i],a[i]}. (su...

  • 快速排序和堆排序

    快速排序 void QuickSort(int array[], int low, int high) { int i = low; int j = high; if (i >j) return; i...

  • 网络流 : 最小割 求 最大权闭合子图

    定义 有一个有向图,每一个点都有一个权值(可以为正或负或0),选择一个权值和最大的子图,使得每个点的后继都在子图里面,这个子图就叫最大权闭合子图。  如下图:    能选的子图有Ø,{4},{3,4},{2,4},{1,2,3,4},它们的权值分别为0,-1,5,-6,4.  所以最大权闭合子图为{3,4},权值为5. 解法 这个问题可以转化为...

  • 最大堆、最小堆Java实现,解决TOP K问题

    一、基础知识 1.1 什么是最大(小)堆 最大堆,最小堆类似,以下以最小堆为例进行讲解。 最小堆是满足以下条件的数据结构: 它是一棵完全二叉树所有父节点的值小于或等于两个子节点的值 1.2 什么是完全二叉树 ...

CSDN

CSDN

中国开发者社区CSDN (Chinese Software Developer Network) 创立于1999年,致力为中国开发者提供知识传播、在线学习、职业发展等全生命周期服务。
堆排序(最大堆)介绍:华为云为您免费提供堆排序(最大堆)在博客、论坛、帮助中心等栏目的相关文章,同时还可以通过 站内搜索 查询更多堆排序(最大堆)的相关内容。| 移动地址: 堆排序(最大堆) | 写博客