排序算法--堆排序

发布于:2024-08-08 ⋅ 阅读:(17) ⋅ 点赞:(0)

其实堆排序已经涉及到一个叫做“树”的数据结构了,它不同于链表、栈、队列等,它是一种非线性的数据结构。那么我们今天不说太多,后面自然会仔细讲解的,今天我们就学会一些基础的概念就行。

一、树结构

相信大家在数学中的求概率中都见过树状图,直到什么是树状图,这样的话,下面就直接上图了:

像这种,除了初始的节点外,每个节点都有且只有一个前驱节点,也可能会有多个后继节点的关系图就是树状图。

1.基本概念

下面引入一些概念:

父节点:又称双亲结点。某节点的前驱节点就是该节点的父节点。

子节点:又称孩子节点。某节点的后继节点就是该节点的子节点。

兄弟节点:父节点相同的两个或多个节点之间互称为兄弟节点。

节点的度:每个节点的子节点数目被称为该节点的度。像上图前两行的节点的度全部为3,也就是该节点拥有直接后继节点的数目。

叶节点:又称终端节点。度为0的节点被称为叶节点,也就是终端节点。

分支节点:又称非终端节点。度不为0的节点被称为非终端节点。

树的度:一棵树的度是所有节点中最大的度。

节点的层次:从根开始为第一层,往下每一个节点层数加一

树的高度(深度):层次的最大值就是树的高度

堂兄弟节点:父节点在同一层的节点且父节点不同的节点互为堂兄弟节点

节点的祖先:从某节点的线路一直向上遍历,遍历经过的所有节点都是该节点的祖先

子孙:某节点之下的所有子树的节点都是该节点的子孙。也就是该节点一直向下遍历,遇到分支分别遍历,经过的所有节点都是该节点的子孙。

森林:互不相交的n棵树(n>=2)组成的集合叫做森林


2.二叉树

如果树的度超过2会比较复杂难以研究。我们经常选取树的度为2的树作为研究对象。这类树又被称为二叉树。二叉树顾名思义,每个节点最多有两个分支。

其中序号1为根节点。2和4所在分支为该树的左子树,3、5、6为该树的右子树。而2和3分别为1的左右子节点,5和6分别为3的左右子节点。但4是2的左节点?还是2的右节点?不知道,所以我们为了明确,下面引出特殊的二叉树:

3.特殊二叉树

特殊的二叉树分为完全二叉树和满二叉树。

满二叉树:除了最后一层的节点度全为0,其余节点的度都是2。这也就是满字的意义。二叉树决定了树的度上限为2,满字代表了节点的度全为2。但二叉树总归要有终端节点的,那就是最后一层的节点,而它们的度全为0。

完全二叉树:完全二叉树在满二叉树的基础上,允许倒数第二层的节点的度不全为0,但是最后一层从左到右的节点必须挨着。这样我们就可以直到度为1的节点的子节点必为该节点的左子节点。

4.二叉树的存储结构

二叉树的存储与其它线性结构类似,都有顺序存储和链式存储两种。但只是为了存储数据的话,我们为什么要用这么复杂的树形结构呢,线性结构存数据不香吗?

增删查改四大操作,二叉树的优势在于查找。存储只是一方面,查找才是二叉树的强项。

二叉树的物理结构是数组,逻辑结构是二叉树,真正实现的时候即使能用两种方式存储,大多数还是用数组存储数据的。接下来我们就开始讲一讲:堆。(这可不是内存的堆区空间的堆,而是一种特殊的数据结构)。


二、堆结构

1.堆的概念

堆就是用满二叉树实现的。堆又分为大根堆和小根堆。

大根堆:父节点永远大于子节点。根节点存储的就是该组数据的最大值。

小根堆:父节点永远小于子节点。根节点存储的就是改组数据的最小值。

2.堆的实现

调整子树

void adjust(vector<int>& v, int _begin, int _end) {
	int father = _begin;//传入的参数就是父节点
	int child = father * 2 + 1;//左子下标
	while (child <= _end) {
		if (child + 1 <= _end && v[child + 1] > v[child]) {
			child++;
		}
		if (v[child] > v[father]) {
			swap(v[child], v[father]);
			father = child;
			child = father * 2 + 1;
		}
		else break;//避免死循环
	}
	return;
}

 初始化堆

void initHeap(vector<int>& v)
{   
    int n = v.size(); 
    for (int i = n / 2 - 1; i >= 0; i--) {
	    int father = i;
	    int child = father * 2 + 1;//左子下标
	    while (child <= n-1) {
		    if (child + 1 <= n-1 && v[child + 1] > v[child]) {
		    	child++;
		    }
		    if (v[child] > v[father]) {
		    	swap(v[child], v[father]);
		    	father = child;
		    	child = father * 2 + 1;
		    }
		    else break;//避免死循环
	    }
	    return;
    }
}
void initHeap(vector<int>& v)
{
    int n=v.size();
    for(int i=n/2-1;i>=0;i--){
        adjust(v,i,n-1);
    }
}

 三、堆排序

1.过程分析

第一步:将待排序数组形成一个堆结构,然后调整至最大堆

(堆结构:左孩子下标是2i+1,有孩子下标是2i+2)

(最大堆的特点:在这个堆结构中,任何一个父节点的值都大于其子节点的值)

第二步:将堆顶元素与待排序数组(假设待排序数组的元素个数为n)最后一个图元素进行交换

swap(&a[0],&a[n-1]);

第三步:待排序数据量减少一个:n--;将待排序数组重新调整最大堆结构,重复第二步,循环n-1次,将所有数据排序完成。

注意:初始化堆(将数组调整成最大堆)从最后一个父节点开始调整(即i=n/2-1)

下面演示数组{20,30,90,40,70,110,60,10,100,50,80}转化为最大堆{110,100,90,40,80,20,60,10,30,50,70}的步骤:

2.代码实现


void HeapSort(vector<int>& v) {//堆结构:完全二叉树
	//初始化阶段:调整至最大堆结构(升序)
	//第一步:获取数组大小
	int n = v.size();
	//第二步:获取堆的最后一个父节点
	int pos_last_parent = n / 2 - 1;
	//第三步:调整堆结构,从最后一个父节点一直到根节点
	for (int i = pos_last_parent; i >= 0; i--) {
		adjust(v, i, n - 1);
		//对每一个部分堆进行调整,从第i个位置开始,到n-1处的最后一个元素结束
	}
    //initHeap(v);
	//阶段结果:堆顶元素就是待排序的最大值

	//排序阶段:交换最大值与待排序的尾元素
	for (int i = n - 1; i >= 1; i--) {
		swap(v[0], v[i]);//交换值
		adjust(v, 0, i - 1);
		//重新调整节点,从根节点0开始,到待排的最后一个元素i-1结束
	}
}

3.算法分析 

时间复杂度:O(nlogn)

稳定性:不稳定