前言

我们已经学习了堆的插入和删除操作，下面我们来学习一下堆排序

其实堆排序很简单，主要有两种实现方法：

方法一：

将元素依次插入到堆中，然后输出堆，此时输出的元素都是有序的。这种方法利用的是堆的特性，因为非常简单，我就不进行代码展示了。

 

方法二：

 

将一个数据源数组传给堆，堆在初始化的时候会把数组的元素依次复制到堆内部数组中，但是注意，此时堆的数据是无需的，那么如何排序呢？就是从第一个不是叶子的节点节点开始，依次进行shitDown操作。

为什么要这么操作呢？为什么要只对非叶子节点进行操作呢？因为叶子是没有子孩子，所以叶子节点可以看成是一个只有一个元素的二叉树，它是有序的。所以我们不需要进行考虑。

那么如何找到第一个非叶子节点呢？当根元素的下标为1的情况下，第一个非叶子节点的下标为 count / 2 ,利用这个规律，我们就可以进行操作了。

没什么难度。大家看一下源码就行了

代码实现

方法二代码：

/*
	 * 二叉堆的构造函数
	 * int [] arr,数据源数组
	 * int size,堆的容量大小
	 * */
	public Heap(int [] arr,int size) {
		if(size <= 0) {
			throw new RuntimeException("size can not be null !");
		}
		int len = arr.length;
		datas = new int [size+1];
		for(int i = 0;i < len;i++) {
			datas[i+1] = arr[i];
		}
		count = len;
		for(int i = count/2;i >= 1;i--) {
			shitDown(i);
		}
	}

完整代码实现

package com.smarking.lzy.part2;

import com.smarking.lzy.part1.SortTestHelper;

/*
 * 用数组实现堆
 * 堆的定义？
 * 二叉堆左右节点和父节点之间的关系？
 * 如何使用数组进行是实现？
 * 
 * 
 * */
public class Heap {
	//定义一个数组用来存储数据
	private int [] datas;
	//定义一个变量来记录当前数据的数量
	private int count;
	
	/*
	 * 二叉堆的构造函数
o	 * int size : 堆的大小
	 * */
	public Heap(int size) {
		if(size <= 0) {
			throw new RuntimeException("size can not be null !");
		}
		count = 0;
		datas = new int [size];
	}
	
	/*
	 * 二叉堆的构造函数
	 * int [] arr,数据源数组
	 * int size,堆的容量大小
	 * */
	public Heap(int [] arr,int size) {
		if(size <= 0) {
			throw new RuntimeException("size can not be null !");
		}
		int len = arr.length;
		datas = new int [size+1];
		for(int i = 0;i < len;i++) {
			datas[i+1] = arr[i];
		}
		count = len;
		for(int i = count/2;i >= 1;i--) {
			shitDown(i);
		}
	}
	
	//获取当前堆的大小
	public int size() {
		if(datas == null) {
			throw new RuntimeException("Heap is null !");
		}else {
			return count;
		}
	}
	
	//判断是否为空
	public boolean isEmpty() {
		if(datas == null || datas.length == 0) {
			return true;
		}else {
			return false;
		}
	}
	
	//最大堆的插入操作
	public void insert(int value) {
		if(count >= datas.length - 1) {
			throw new RuntimeException("Heap is full !");
		}
		
		datas[count+1] = value;
		count+=1;
		
		//对count位置的元素进行调整
		shitUp(count);
	}
	
	/**
	 * 对指定位置的元素进行重新调整，使其能够符合最大堆的定义
	 * 原理：不断和它的父节点比较，如果都比它大，就退出。反之，则进行交换，然后重复操作
	 * */
	private  void shitUp(int index) {
		while(index > 1 && datas[index/2] < datas[index]) {
			int val = datas[index];
			datas[index] = datas[index/2];
			datas[index/2] = val;
			index = index/2;
		}
	}
	
	//弹出最大元素
	public int delete() {
		int result = datas[1];
		datas[1] = datas[count];
		count-=1;
		shitDown(1);
		return result;
	}
	
	/**
	 * 对指定位置的元素进行重新调整，使其能够符合最大堆的定义
	 * 原理：不断和它的左右孩子比较，如果都比它小，就退出。反之，则选择一个最大的进行交换，然后重复操作
	 * */
	private void shitDown(int index) {
		//假如左节点还存在，就循环
		while(index*2 <= count) {
			int j = index*2;
			//判断是否有右孩子,然后判断是否符合交换条件
			if(j+1 <= count && datas[j+1] > datas[j]) {
				if(datas[index] > datas[j+1]) {
					return;
				}
				int val = datas[j+1];
				datas[j+1] = datas[index];
				datas[index] = val;
				j += 1;
			}else {
				if(datas[index] > datas[j]) {
					return;
				}
				
				int val = datas[j];
				datas[j] = datas[index];
				datas[index] = val;
			}
			
			index = j;
		}
	}
	
	
	public void printHeap() {
		if(isEmpty()) {
			throw new RuntimeException("Heap is null !");
		}
		
		for(int i = 1;i <= count;i++) {
			System.out.println("index:"+i+";value:"+datas[i]);
		}
	}
	
	public static void main(String[] args) {
		int testTime = 1000;
		int maxValue = 100;
		int maxSize = 10000;
		boolean success = true ;
		Heap heap = null;
		for(int i = 0;i < testTime;i++) {
			int [] arr1 = SortTestHelper.generateRandomArray(maxSize, maxValue);
			int [] arr2 = SortTestHelper.copyArray(arr1);
			int [] arr3 = SortTestHelper.copyArray(arr1);
			heap = new Heap(arr1,arr1.length);
			SortTestHelper.comparator(arr2);
			if(!SortTestHelper.isEqual(arr2, heap)) {
				success = false;
				SortTestHelper.printArray(arr1);
				break;
			}
		}
		
		if(success) {
			System.out.println("Nice!!!");
		}else {
			System.out.println("Fuck!");
		}
	}
}