重点算法排序之堆排序（下篇）

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6

 

文章目录

一、堆排序的概念

1、1 堆的基本概念

1、2 堆的特性

二、堆排序的思路及代码实现

2、1 建堆

2、2 向下调整算法详解

2、3 建完堆后进行堆排序

2、3、1 排升序建大堆

2、3、2 建大堆后进行堆排序 

三、堆排序的例题

2、1 例题1堆排序   

2、2 例题2模拟堆

 四、总结 

标题重点算法排序之堆排序下篇

作者@Ggggggtm

寄语与其忙着诉苦不如低头赶路奋路前行终将遇到一番好风景

  我们已经讲述了快速排序和归并排序快速排序和归并排序详解文章链接重点算法排序之快速排序、归并排序上篇我们本篇文章来详细讲述以下堆排序。堆排序的主要内容有最大堆大顶堆、最小堆小顶堆、通过孩子找父亲、通过父亲找孩子、向下调整算法建堆。下面我会给大家一一介绍。

一、堆排序的概念

1、1 堆的基本概念

  堆一般指的是二叉堆顾名思义二叉堆是完全二叉树或者近似完全二叉树。

  堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。 我们是用一个数组来表示一个堆。如下图

1、2 堆的特性

  堆的特性有如下几点

  • 堆是一棵完全二叉树。
  • 每个父亲节点的值都大于或等于其子节点的值为最大堆反之为最小堆。
  • 下标为 i 的结点的父结点下标为(i-1)/2。
  • 其下标为i的左右子结点分别为 (2i + 1)、(2i + 2)。

  我们上述的后两点讲述了通过孩子找父亲、通过父亲找孩子的方法。那么给出一个乱序的数组我们怎么建出来一个堆呢我们接着往下看。

二、堆排序的思路及代码实现

2、1 建堆

  我们想用堆对数组进行排序我们得首先有一个堆。那么问题来了当给出我们一个乱序的数组时我们怎么建出一个堆呢这里就用到了我们的向下调整算法。

2、2 向下调整算法详解

  我们在这里用小堆来讲述向下调整算法的实现。那到底什么是向下调整算法呢我们先看一下向下调整算法的概念。

  向下调整算法就是调整结点的位置使调整的路径上满足大堆或小堆的条件以调整小堆为例对某一结点为根结点的堆进行向下调整首先找到两个子结点中最小的那一个结点然后与根结点进行比较如果比根结点小则交换交换后使新的根结点为被交换结点的位置对此位置所在结点继续进行相同的比较与交换直到调整的结点不在堆的合法范围内或子结点没有比根结点小为止此时这样的一个过程就叫做向下调整因为它调整的方向是向下的。我们具体看一个例子。如下图

 

  注意建小堆用向下调整算法用的前提为左子树和右子树均为小堆。建大堆同理。

  我们看一下向下调整算法的代码实现如下

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int arr[], int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//默认左孩子
	while (child < n)
	{
		if (child+1<n && arr[child + 1] > arr[child])//要考虑到有孩子存在不
		{
			child += 1;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

   那要是左右子树不是小堆呢如下图

  我们看到上述的完全二叉树并不是一个堆我们想要对第一个元素3进行向下调整算法但是3的左右子树并不是小堆那对3就不能用向下调整算法了。怎么办呢我们不妨从最后的一颗子树开始使用向下调整算法。 也就是从8开始依次往前使用向下调整算法即可。

  我们再看建堆的整个代码

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int arr[], int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//默认左孩子
	while (child < n)
	{
		if (child+1<n && arr[child + 1] > arr[child])//要考虑到有孩子存在不
		{
			child += 1;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int arr[], int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
}

2、3 建完堆后进行堆排序

2、3、1 排升序建大堆

  我们知道大堆的根节点是最大的。同时根节点总比子节点大。那为什么排升序要建大堆呢假如是建的小堆最小数在堆顶最小的数相当于被选出来了。那么在剩下的始终再去 选数。但是剩下的树结构就乱了如下图   此时我们需要重新建堆才能选出下一个最小的数。建堆的时间复杂度为On这样的效率就很低了。

    我们建大堆大堆第一个元素是最大的。我们把第一个元素和最后一个元素交换那么最大的数就到了最后面。然后把最大的数不看做堆里面的数据此时剩下的数据的结构并没有乱如下图

  再对第一个数进行数向下调整又成为了一个大堆反复此操作即可排序完成。

2、3、2 建大堆后进行堆排序 

  由上述我们知道当我们要排升序时我们要建的是大堆。当建完大堆后我们就要进行堆排序。建完堆交换第一个数据合作后一个数据再对第一个数据进行向下调整。向下调整完后有成为一个大堆再次交换、向下调整。当每个数据都向下调整后我们的数据就称为了升序。我们看代码的实现

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void AdjustDown(int arr[], int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//默认左孩子
	while (child < n)
	{
		if (child+1<n && arr[child + 1] > arr[child])//要考虑到有孩子存在不
		{
			child += 1;
		}
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int arr[], int n)
{
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}


	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}
void Print(int arr[], int n)
{
	int i = 0;
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}
void TestSort()
{
	int arr[10] = { 0,9,8,7,6,5,4,3,2,1 };
	int n = 10;
	HeapSort(arr, n);
	Print(arr, n);
}
int main()
{
	TestSort();
	return 0;
}

   以上即为整个堆排序的过程。我们不妨来看几道堆排序的例题。

三、堆排序的例题

2、1 例题1堆排序   

堆排序

输入一个长度为 n 的整数数列从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数表示整数数列。

输出格式

共一行包含 m 个整数表示整数数列中前 m 小的数。

数据范围

1≤m≤n≤10e5  1≤m≤n≤10e5
1≤数列中元素≤10e9   1≤数列中元素≤10e9

输入样例

5 3
4 5 1 3 2

输出样例

1 2 3

这道题我们用堆排序来做一下我们看答案

#include<iostream>
#include <algorithm>
using namespace std;

const int N=100010;

int cnt,q[N];
int n,m;

void down(int x)
{
    int t=x;
    if(x*2+1<cnt&&q[x*2+1]<q[t])
        t=x*2+1;
    if(x*2+2<cnt&&q[x*2+2]<q[t])
        t=x*2+2;
    if(t!=x)
    {
        swap(q[t],q[x]);
        down(t);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&q[i]);
    }
    cnt=n;
    for(int i=n-1-1>>1;i>=0;i--)
    {
        down(i);
    }
    while(m--)
    {
        printf("%d ",q[0]);
        q[0]=q[cnt-1];
        cnt--;
        down(0);
    }
    return 0;
}

2、2 例题2模拟堆

维护一个集合初始时集合为空支持如下几种操作

  1. I x插入一个数 xx
  2. PM输出当前集合中的最小值
  3. DM删除当前集合中的最小值数据保证此时的最小值唯一
  4. D k删除第 kk 个插入的数
  5. C k x修改第 kk 个插入的数将其变为 xx

现在要进行 N 次操作对于所有第 2 个操作输出当前集合的最小值。

输入格式

第一行包含整数 N。

接下来 NN 行每行包含一个操作指令操作指令为 I xPMDMD k 或 C k x 中的一种。

输出格式

对于每个输出指令 PM输出一个结果表示当前集合中的最小值。

每个结果占一行。

数据范围

1≤N≤10e5  1≤N≤10e5
−10e9≤x≤10e9  −10e9≤x≤10e9
数据保证合法。

输入样例

8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM

输出样例

-10
6

  我们这道题的所有操作都可以用向下调整或向上调整都可以玩成。我们看一下答案

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
const int N=100010;
int h[N],qh[N],hq[N],cnt;
void heap_swap(int a,int b)
{
    swap(qh[hq[a]],qh[hq[b]]);
    swap(hq[a],hq[b]);
    swap(h[a],h[b]);
}
void down(int u)
{
    int t=u;
    if(u*2<=cnt&&h[u*2]<h[t])
        t=2*u;
    if(u*2+1<=cnt&&h[u*2+1]<h[t])
        t=2*u+1;
    if(t!=u)
    {
        heap_swap(t,u);
        down(t);
    }
    
}
void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}
int main()
{
    int n,m=0;
    scanf("%d",&n);
    while(n--)
    {
        char op[5];
        int k,x;
        scanf("%s",op);
        if(!strcmp(op,"I"))
        {
            scanf("%d",&x);
            m++;
            cnt++;
            qh[m]=cnt;
            hq[cnt]=m;
            h[cnt]=x;
            up(cnt);
        }
        else if(!strcmp(op,"PM"))
        {
            printf("%d\n",h[1]);
        }
        else if(!strcmp(op,"DM"))
        {
            heap_swap(1,cnt);
            cnt--;
            down(1);
        }
        else if(!strcmp(op,"D"))
        {
            scanf("%d",&k);
            k=qh[k];
            heap_swap(k,cnt);
            cnt--;
            down(k);
            up(k);
        }
        else
        {
            scanf("%d%d",&k,&x);
            k=qh[k];
            h[k]=x;
            down(k);
            up(k);
        }
    }
    return 0;
}

 四、总结

  对排序中重点是要熟知向下调整算法并且知道排升序建大堆还是小堆。这里给大家总结出各个排序的时间复杂度、空间复杂度、是否稳定性。需要掌握的。

  堆排序的讲解就到这里希望以上内容对你有所帮助。

  感谢阅读ovo~

阿里云国内75折 回扣 微信号：monov8
阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6
返回列表

上一篇：[ Azure - Database ] What the f**k is going on Azure Database for MySQL -- Single Server ?

下一篇：stm32f103最小系统板详细介绍

“重点算法排序之堆排序（下篇）” 的相关文章

程序设计原则-单一职责原则1年前 (2023-02-02)
Nacos学习：二、配置中心1年前 (2023-02-02)
普冉PY32系列(二) Ubuntu GCC Toolchain和VSCode开发环境1年前 (2023-02-02)
不懂编译原理？本文教你从零实现最简编译模型！1年前 (2023-02-02)
Loj 507 接竹竿 题解1年前 (2023-02-02)
基于STM32的OLED多级菜单GUI实现（简化版智能手表）1年前 (2023-02-02)
WPF-3D图形1年前 (2023-02-02)
计算机网络实验——华为eNSP模拟器常用命令总结（总结的非常详细( •̀ .̫ •́ )✧快来看啊）_华为ensp命令大全1年前 (2023-02-02)
学习笔记——安卓的下载路径；创建一个空的安卓project；Android中的日志工具划分1年前 (2023-02-02)
01背包问题的三种求解方法——动态规划、回溯法、分支限界法的具体思路介绍及对比1年前 (2023-02-02)

阿里云国际版