八大排序之堆排序--堆排序 java

灰太狼 2022-05-11 06:20 263阅读 0赞

## 堆排序及其优化 java ##

[https://www.cnblogs.com/CherishFX/p/4643940.html][https_www.cnblogs.com_CherishFX_p_4643940.html]  
堆排序，是利用堆结构进行排序，一般是利用最大堆，即根节点比左右两个子树的节点都大。  
堆排序是一种树形选择排序方法，它的特点是：在排序的过程中，将array\[0，…，n-1\]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大（最小）的元素。

> 1、什么是堆？

堆是有如下特点的二叉树：  
1）它是完全二叉树。即除了树的最后一层节点不需要是满的，其他的每层从左到右完全是满的。  
2）它常常是数组实现的。  
3）堆中的每个节点都必须满足堆的条件。  
每个节点的关键字都不大于其子节点的关键字，这种堆称为小根堆。  
每个节点的关键字都不小于其子节点的关键字，这种堆称为大堆根。本文采用此结构演示  
综上所述，堆是一棵顺序存储的按照特定规则的完全二叉树。

数组的节点的索引为index，则：  
1）它的父节点的下标为：（index-1）/2  
2）它的左子节点的下标为：2*index + 1  
3）它的右子节点的下标为：2*index + 2

> 2、堆与二叉搜索树的不同：

堆和二叉搜索树相比是弱序的。在二叉搜索树中，所有节点的关键字大于其左子树的关键字，小于其右子树的关键字。但是在堆中，每个节点都不小于其子节点，即从 根到叶子节点的每条路径都是降序排列的。

> 3、插入操作

1）将新增节点插入到数组最后第一个空着的单元中，数组容量加一。  
2）向上筛选：与父节点比较，如果大于父节点的关键字，则与父节点交换。依次重复上述动作，直到父节点的关键字大于目标节点为止。

> 4、删除操作

1）移走根节点。  
2）把最后一个节点移动到根的位置上。  
3）一直向下筛选这个节点，在两个孩子中找到最大值，如果小于最大值，两者交换，直到大于它的子节点小于它的父节点为止。

> 5、堆排序：（大根堆）

①将存放在array\[0，…，n-1\]中的n个元素建成初始堆；  
　　②将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；  
　　③但此时堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再重复第②③步，直到堆中仅剩下一个元素为止。

> 堆排序算法的性能分析：

空间复杂度:o(1)；

时间复杂度:建堆：o(n)，

每次调整o(log n)，故最好、最坏、平均情况下：o(n\*logn);

> 稳定性：不稳定

##  ##

> 构建大根堆

// 构建大根堆：将array看成完全二叉树的顺序存储结构
    private static int[] buildMaxHeap(int[] array) {
    	// 从最后一个节点array.length-1的父节点（array.length-1-1）/2开始，直到根节点0，反复调整堆
    	for (int i = (array.length - 2) / 2; i >= 0; i--) {
    		adjustDownToUp(array, i, array.length);
    	}
    	return array;
    }

> 调整树形结构

// 将元素array[k]自下往上逐步调整树形结构
    private static void adjustDownToUp(int[] array, int k, int length) {
    	int temp = array[k];
    	for (int i = 2 * k + 1; i < length; i = 2 * i + 1) {
            	// i为初始化为节点k的左孩子，沿节点较大的子节点向下调整
    		if (i < length-1 && array[i] < array[i + 1]) { 
               		 // 取节点较大的子节点的下标
    			i++; // 如果节点的右孩子>左孩子，则取右孩子节点的下标
    		}
    		if (temp >= array[i]) { 
    		    // 根节点 >=左右子女中关键字较大者，调整结束
    			break;
    		} else { // 根节点 <左右子女中关键字较大者
                // 将左右子结点中较大值array[i]调整到双亲节点上
    			array[k] = array[i];
    			k = i; // 【关键】修改k值，以便继续向下调整
    		}
    	}
    	array[k] = temp; // 被调整的结点的值放在最终位置
    }

> 堆排序

// 堆排序
    public static int[] heapSort(int[] array) {
    	array = buildMaxHeap(array); // 初始建堆，array[0]为第一趟值最大的元素
    	for (int i = array.length - 1; i > 1; i--) {
    		// 将堆顶元素和堆低元素交换，
    		// 即得到当前最大元素正确的排序位置
    		int temp = array[0]; 
    		array[0] = array[i];
    		array[i] = temp;
    		adjustDownToUp(array, 0, i); // 整理，将剩余的元素整理成堆
    	}
    	return array;
    }

> 插入操作

// 插入操作:向大根堆array中插入数据data
    public int[] insertData(int[] array, int data) {
    	array[array.length - 1] = data; // 将新节点放在堆的末端
    	int k = array.length - 1; // 需要调整的节点
    	int parent = (k - 1) / 2; // 双亲节点
    	while (parent >= 0 && data > array[parent]) {
    		array[k] = array[parent]; // 双亲节点下调
    		k = parent;
    		if (parent != 0) {
    			parent = (parent - 1) / 2; // 继续向上比较
    		} else { // 根节点已调整完毕，跳出循环
    			break;
    		}
    	}
    	array[k] = data; // 将插入的结点放到正确的位置
    	return array;
    }

> 删除堆顶元素操作

// 删除堆顶元素操作
    public int[] deleteMax(int[] array) {
    	// 将堆的最后一个元素与堆顶元素交换，堆底元素值设为-99999
    	array[0] = array[array.length - 1];
    	array[array.length - 1] = -99999;
    	// 对此时的根节点进行向下调整
    	adjustDownToUp(array, 0, array.length);
    	return array;
    }

> 测试

//测试
    public static void main(String args[]) {
    	HeapSort hs = new HeapSort();
    	int[] array = { 87, 45, 78, 32, 17, 65, 53, 9, 122 };
    	System.out.print("构建大根堆：");
    	hs.toString(hs.buildMaxHeap(array));
    	System.out.print("\n" + "删除堆顶元素：");
    	hs.toString(hs.deleteMax(array));
    	System.out.print("\n" + "插入元素63:");
    	hs.toString(hs.insertData(array, 63));
    	System.out.print("\n" + "大根堆排序：");
    	hs.toString(hs.heapSort(array));
    }

> 排序：

import java.util.Scanner;
    
    public class Main7 {
    	public static void main(String[] args) {
    		Scanner sc = new Scanner(System.in);
    		// 输入带排序数组，以空格分开
    		String[] st = sc.nextLine().split(" ");
    		int[] arr = new int[st.length];
    		for (int i = 0; i < st.length; i++) {
    			arr[i] = Integer.parseInt(st[i]);
    		}
    		heapSort(arr);
    		for (int i = 0; i < 8; i++) {
    			System.out.print(arr[i] + " ");
    		}
    	}
    	
    	// 堆排序
    	public static void heapSort(int[] arr) {
    		int length = arr.length;
    		// 此循环为了初始化堆
    		for (int i = (length - 1) / 2; i >= 0; i--) {
    			heapAdjust(arr, i, length);
    		}
    		for (int i = length - 1; i >= 0; i--) {
    			// 交换堆顶元素H[0]和堆中最后一个元素
    			int temp = arr[i];
    			arr[i] = arr[0];
    			arr[0] = temp;
    			// 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
    			heapAdjust(arr, 0, i);
    		}
    	}
    
    	public static void heapAdjust(int[] arr, int i, int length) {
    		int temp = arr[i]; // 待调整位置结点
    		int child = 2 * i + 1; // 左孩子结点的位置
    		while (child < length) {
    			if (child + 1 < length && arr[child + 1] > arr[child]) { // 如果右孩子比左孩子大
    				child++; // 右孩子结点位置
    			}
    			if (arr[i] < arr[child]) { // 如果待调整位置结点小于孩子结点中最大的
    				arr[i] = arr[child]; // 将孩子结点上移代替父结点
    				i = child; // 新的待调整结点位置
    				child = 2 * i + 1; // 新的左孩子结点位置
    			} else {
    				break; // 反之不需要调整
    			}
    			arr[i] = temp; // 将待调整结点的值给新的待调整结点
    		}
    	}
    }

[https_www.cnblogs.com_CherishFX_p_4643940.html]: https://www.cnblogs.com/CherishFX/p/4643940.html