堆排序是一种动态排序,它基于堆这种数据结构。堆分为小根堆和大根堆。堆的实质是一棵二叉树,只不过使用的是连续存储。堆分为小根堆和大根堆。小根堆的特点是根结点最小,其每一个子堆也满足这个特点。相反,大根堆的特点是根结点最大,且其每一个子堆也满足这一个特点。
堆排序的实质是堆顶元素出堆,而后再维护堆的特点进行调整,继续出堆直至堆为空,排序完成。可按如下步骤进行:
1. 初始建堆。根据序列构造完全二叉树,并进行调整,以满足堆的特点,由于是升序排序,所以建立小根堆。因为每一个子堆也必须满足小根堆的特点,所以需要对结点自底向上进行调整。叶子结点显然已满足,所以直接从最后一个叶子结点的父节点开始调整,也就是从序号为 n/2 的位置开始调整到根结点位置(位置为 1)结束。
对于每一个子堆的调整,其实质是可能存在孩子结点小于根结点,因而需要作向下调整。调整的方法是先保存根结点,再取其孩子结点(如果存在两个孩子结点则取其最小的一个),若这个结点值小于根结点值,则没有调整的必要,调整结束。否则,将这个结点值赋值给根结点,位置也赋值给根结点的位置,继续向下一层的孩子结点进行比较,直到调整到叶结点或者已经满足特性。
2. 堆顶元素出堆。出堆的过程是将堆顶元素和堆底元素交换,并且堆长度减 1。由于交换后,堆特性可能已经被破坏,因此需要从新调整根结点的位置,重新向下调整。出堆操作不断进行下去,直至堆为空,排序结束。输出出堆的元素,即为升序序列。
仍然以序列 4,3,1,2,5 为例:
1. 初始建堆,堆长为 5
初始二叉树为:
初始二叉树
结点 3 向下调整。由于下层孩子结点 2 小于 3,故 2 和 3 交换:
结点 3 调整
调整后序号 2 为根结点的子堆已满足小根堆特点。
结点 4 向下调整。由于下层孩子结点,最小的是结点 1,则将 1 和 4 交换:
结点 4 向下调整
可见此时已完全满足小根堆特点。
- package com.fairy.InnerSort;
- import java.util.Scanner;
- /**
- * 定义堆数据结构
- * @author Fairy2016
- *
- */
- class Heap {
- int data[]; //元素
- int length; //堆长
- int max = 100; //堆空间大小,如不够每次再加
- //初始建堆
- void InitBuildHeap(int a[], int n) {
- int i;
- data = new int[n + 1];
- length = n;
- for (i = 1; i <= n; i++) {
- data[i] = a[i];
- }
- //从最后一个结点的父节点开始调整
- for (i = n / 2; i > 0; i--) {
- AdjustDown(i);
- }
- }
- //向下调整,以保持堆的特性以及子堆的特性
- void AdjustDown(int k) {
- data[0] = data[k];
- for (int i = 2 * k; i <= length; i *= 2) {
- if (i < length && data[i] > data[i + 1]) i++; //由于一个结点的子节点可能有两个,还需比较大小
- if (data[0] < data[i]) {
- break; //如果其子节点都比它大,那么无须调整
- } else {
- data[k] = data[i];
- k = i; //向上赋值,更新结点位置
- }
- }
- data[k] = data[0]; //赋值到调整后确定的位置
- }
- //向上调整,用于新入堆元素后保持堆的特性
- void AdjustUp(int k) {
- data[0] = data[k];
- for (int i = k / 2; i > 0; i /= 2) {
- if (data[0] > data[i]) {
- break; //如果父结点都比它小,那么无须调整
- } else {
- data[k] = data[i];
- k = i; //向下赋值,更新结点位置
- }
- }
- data[k] = data[0];
- }
- //元素出堆
- int PopupHeap() {
- int e = data[1];
- //交换堆顶和堆底元素
- data[1] = data[length];
- data[length] = e;
- //堆长度减1
- length--;
- //需要调整以满足堆特性
- AdjustDown(1);
- return e;
- }
- //判断堆是否已空
- boolean IsEmpty() {
- if (length >= 1) {
- return false;
- }
- return true;
- }
- //元素入堆
- void PushHeap(int e) {
- //如果空间不够,需从新分配
- if (length == data.length - 1) {
- int capa = max;
- while (capa <= length + 1) {
- capa += max;
- }
- int help[] = new int[length];
- for (int i = 1; i <= length; i++) {
- help[i - 1] = data[i];
- }
- data = new int[capa];
- for (int i = 1; i <= length; i++) {
- data[i] = help[i - 1];
- }
- data[++length] = e; //新元素加入到堆底
- } else {
- data[++length] = e; //新元素加入到堆底
- }
- AdjustUp(length);
- }
- }
- /**
- * 堆排序
- * @author Fairy2016
- *
- */
- public class HeapSort {
- public static void sort(int a[], int n) {
- Heap heap = new Heap();
- heap.InitBuildHeap(a, n);
- while (!heap.IsEmpty()) {
- System.out.print(heap.PopupHeap() + " ");
- }
- }
- public static void main(String args[]) {
- int n;
- int a[];
- Scanner scanner = new Scanner(System. in );
- while (scanner.hasNext()) {
- n = scanner.nextInt();
- if (n > 0) {
- a = new int[n + 1];
- for (int i = 1; i <= n; i++) {
- a[i] = scanner.nextInt();
- }
- sort(a, n);
- }
- }
- scanner.close();
- }
- }
堆排序的时间复杂度由出堆操作和调整维护堆特性操作嵌套决定,出堆操作 o(n),调整操作 o(log2(n))。所以时间复杂度为 o(n*log2(n))。时间复杂度还算可以,但由于其用到了堆这个数据结构,空间复杂度为 o(n),相对来说不如快速排序。
堆的应用远远不止堆排序,而是作为一种重要的数据结构(优先队列)应用在实际开发中。本文虽然是简单的堆排序,但代码中对于对这种数据结构还是进行了封装,包括其插入元素操作。其实无论是入堆还是出堆,元素操作之后还是要维护堆的特性不变,即大根堆仍然是大根堆,小根堆仍然是小根堆。更多关于堆的相关应用,在后面的贪心算法和分支限界算法文章会继续提到。
来源: http://www.jianshu.com/p/758595b2915e