龙空技术网

再也不怕面试官问我堆排序了

Mikasoi 114

前言:

当前兄弟们对“最大堆和最小堆原理”可能比较着重,你们都需要学习一些“最大堆和最小堆原理”的相关文章。那么小编也在网络上汇集了一些有关“最大堆和最小堆原理””的相关资讯,希望大家能喜欢,小伙伴们快快来学习一下吧!

前提

面试中经常会遇到对堆排序的考察,比如阿里巴巴2016研发工程师笔试题之一:

将整数数组(7-6-3-5-4-1-2)按照堆排序的方式原地进行升序排列,请问在第一轮排序结束之后,数组的顺序是_____。

不了解堆排序的小伙伴此时就会比较尴尬了。

那么到底什么是堆排序呢?它的原理是什么?代码又怎么实现呢?

什么是堆

在介绍堆排序之前,先让我们来了解一下堆及其属性:

堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

堆中某个节点的值总是不大于或不小于其父节点的值;堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

堆是非线性数据结构,相当于一维数组,有两个直接后继。

堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆。

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)

若将和此次序列对应的一维数组(即以一维数组作此序列的存储结构)看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有非终端结点的值均不大于(或不小于)其左、右孩子结点的值。由此,若序列{k1,k2,…,kn}是堆,则堆顶元素(或完全二叉树的根)必为序列中n个元素的最小值(或最大值)。

堆排序

堆排序(Heapsort)是利用堆这种数据结构而设计的一种排序算法,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。堆排序的流程:

将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行1-2步骤,直到整个序列有序。动图演示

代码实现

void adjuctHeap(int i, int arr[], int count) {	int tmp;	int max;	// 条件判断检测是否到了叶子节点	while (i <= count / 2 - 1) 	{		//父节点索引为i时,左子节点下标为2i+1,右子节点下标为2i+2		//总数为偶数时,最后一个父节点没有右子节点,此时tmp置为0		tmp = 2 * i + 2 >= count ? 0 : arr[2 * i + 2];		//max值:左右子节点中更大的那个节点的下标		max = arr[2 * i + 1] >= tmp ? 2 * i + 1 : 2 * i + 2;		//如果子节点比父节点大,则交换父子节点的值		if (arr[max] > arr[i])		{			tmp = arr[max];			arr[max] = arr[i];			arr[i] = tmp;			//父子节点交换完以后,要判断新的子节点下面是否也有子节点,如果有的话也要进行相同的调整			i = max;		}		else			break;	}}void heapSort(int arr[], int count) {	int i;	int tmp;	//停留在构造成功大根堆的前一步。 count / 2 - 1 表示倒数第一个非叶子节点	for (i = count / 2 - 1; i > 0; i--)              		adjuctHeap(i, arr, count);	while (count > 1) 	{		adjuctHeap(0, arr, count);                     //构造大根堆		tmp = arr[0];								   //取出第一个值,及最大值		arr[0] = arr[count - 1];                       //调整最大值到最后的位置		arr[count - 1] = tmp;		count--;                                       //末尾往前移动一位	}}

平均时间上,堆排序的时间常数比快排要大一些,因此通常会慢一些,但是堆排序最差时间也是O(nlogn)的,这点比快排好。

结束语

至此,十种常见的排序算法都已经整理完毕,如果中间有什么写错或者笔误的地方还劳烦大家批评指正,共同进步。

标签: #最大堆和最小堆原理