概念:

实现方法(java):

可以自己写一个类,包含左节点和右节点,但是在这里我并没有使用这种方法,却用了一种比较经典的方法,使用数组来实现这个最大堆,其中我并没有使用下标为0的位置,是从1开始的.

1. 通过构造方法在插入时就保持整个数组为最大堆;
2. 将堆中的最大值拿出,并使数组实时保持最大堆;
3. 实现未经过优化的堆排序,对一个无序数组进行堆排序;

性质:

根节点的关键字既大于或等于左子树的关键字值，又大于或等于右子树的关键字值

核心方法:

1. shiftUp() :在动态的插入数据时保持整体满足最大堆
2. shiftDown(int i) :使数组中以i为下标的堆满足最大堆

结果截图:

java数据结构--最大堆

代码展示:

public class Main { public static void main(String args[]) { Tools tools = new Tools(); //工具类,用于创建随机数数组 //测试1:动态插入数据 System.out.println("1:动态插入数据,获得随机数组并打印"); int[] data = tools.create_int_random(20, 10, 99); for (int i = 0; i < data.length; i++) { System.out.print(data[i] + " "); } //获得随机数组,而且打印初始数组 MaxHeap maxHeap = new MaxHeap(); System.out.println(); maxHeap.insert(data); System.out.println("动态插入后的数组"); maxHeap.print_data(); //将构成的最大堆打印并验证 System.out.println(); System.out.println(); //测试2:将堆中最大的值弹出,并实时保持数组满足最大堆 System.out.println("2:将堆中最大的值弹出,并实时保持数组满足最大堆"); for (int i = 0; i < data.length; i++) { System.out.print(maxHeap.get_Max() + " "); } System.out.println(); //测试3:未优化的堆排序 System.out.println("3:获得随机数组并打印"); int[] data1 = tools.create_int_random(20, 10, 99); for (int i = 0; i < data1.length; i++) { System.out.print(data1[i] + " "); } MaxHeap maxHeap1 = new MaxHeap(data1, data1.length); System.out.println("打印结果"); maxHeap1.print_data_as_array(); } } class MaxHeap { private int data[]; private int count = 0; MaxHeap(int number) { data = new int[number]; } MaxHeap() { data = new int[200]; } /** * 作为检测堆排序的构造方法 * * @param arr * @param number */ MaxHeap(int[] arr, int number) { data = new int[number + 1]; count = number; for (int i = 0; i < arr.length; i++) { data[i + 1] = arr[i]; } for (int i = count / 2; i >= 1; i--) { shifDown(i); } } void insert(int[] num) { int item; for (int i = 0; i < num.length; i++) { item = num[i]; count++; data[count] = item; shiftUp(item); } } /** * 返回最大值 */ int get_Max() { if (count > 0) { int resoult = data[1]; data[1] = data[count]; count--; shifDown(1); return resoult; } return -1; } /** * 在动态的插入数据时保持整体满足最大堆 * * @param num */ private void shiftUp(int num) { int position = count / 2; while (data[position] < num && position != 0) { //让 data[count/2] 与data[count] 交换位置,其中data[count] 之前是num int middle = data[position]; data[position] = num; data[count] = middle; //如果没有下面这步的话,不会进行二次的变化 num = data[position]; position /= 2; } } /** * 使数组中以num为下标的堆满足最大堆 * * @param num */ private void shifDown(int num) { while (2 * num <= count) { int j = 2 * num; //j 为要进行交换的下标 if (j + 1 <= count && data[j + 1] > data[j]) { j += 1; } if (data[num] >= data[j]) { break; } /*交换data[num]与data[j]*/ int middle = data[num]; data[num] = data[j]; data[j] = middle; num = j; } } /** * 打印结果 */ void print_data() { int number = 0; int line = 1; for (int i = 1; i < count; i++) { System.out.print(data[i] + " "); number++; if (number == line) { System.out.println(); line = line * 2; number = 0; } } } void print_data_as_array() { for (int i = 1; i < data.length; i++) { System.out.print(data[i] + " "); } } }