c 语言 堆的解析(自我理解)!!!堆排序,建堆

2023-12-13 04:23:16

目录

1.堆是什么?

2.堆的实现和接口。(小堆)

1.头文件

2.初始化

3.摧毁

4.向上调整(重点)

5.向下调整(重点)

6.插入(重点)

7.删除(重点)

8.头元素

9.元素个数

10.判空

3.堆的排序。

堆排序的源代码和实现


1.堆是什么?

首先先看一个图片

小顶堆的意思就是顶 的元素最小,两个子节点的元素要大于父节点。大顶堆同理。

小顶堆就像是一个金字塔。第一层很小,然后后面是依次增大,就像社会人才金字塔图一样。

大顶堆就可以想做,每个人的财富拥有值的金字塔图,上层人的钱很多,而底层的人钱最少。

其次关于堆,其实堆在通常情况下是一个完全二叉树 (只有最底层的节点没有充满的二叉树,全充满的也属于完全二叉树叫做满二叉树)

那堆能干嘛呢,首先堆是可以用来排序的,而且排序的时间也是较快,处于(n*logn)这个层级。?

?还有一个就是在频繁的出队和入队时,用堆是一个不错的选择。如果用数组和链表来完成pop和push时,时间复杂度是O(n)而用 堆就是O(log n)。

在一个堆中通常用parent 和 child 来表示父节点和子节点。堆通常都是用数组来实现的。

通过上图可以看出堆的父节点如果为0的话,子节点就是1 和 2.就可以推导出公式

child = parent * 2 +1 或者 parent *?2 + 2。parent = child??/ 2。

2.堆的实现和接口。(小堆)

1.头文件

#define _CRT_SECURE_NO_WARNINGS  1
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
#include<time.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
void Swap(int* C, int* P);
void AdjustUP(int* a, int size);//向上调整
void AdjustDown(HPDataType* a, int size,int parent);//向下调整
void HPInit(HP* hp);//初始化
void HPDestroy(HP* hp);//摧毁
void HeapPush(HP* hp, HPDataType x);//加入数据
void HeapPop(HP* hp);//删除数据
HPDataType HeapTop(HP* hp);//查找头元素
int HeapSize(HP* hp);//有效元素个数
bool HeapEmpty(HP* hp);//判空

堆的底层和顺序表的底层很像,但二者也不是相同。

size 的意思是目前元素的个数

capacity是当前开辟的空间的容量?

2.初始化

void HPInit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

3.摧毁

void HPDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

4.向上调整(重点)

void AdjustUP(int* a,int Child)
{
	assert(a);
	int Parent = (Child - 1) / 2;
	while (Child > 0)
	{
		
		if (a[Child] < a[Parent])
		{
			Swap(&(a[Child]), &(a[Parent]));
		}
		else
		{
			break;
		}
		Child = (Child - 1) / 2;
		Parent = (Parent - 1) / 2;
	}
}

关于向上调整实际上就是,把选定的Child位置元素,以大堆或小堆的方式向上调整。

?因为向上调整是从孩子的位置开始向父亲的位置开始调整的,因为向上嘛,如果是父亲调儿子辈分就乱了。所以传入进来的 child 。然后 child > 0 ,是为了让 最后 孩子走到顶就是 0 的位置以后 这时才将所有的父节点比较结束。

因为实现的是小堆,如果子节点的值小于父节点就交换二者的值。出现 大于父节点的值就break。child = (child - 1)/2 是为了让子节点成为父节点,而 parent = (parent - 1)/2是为了让父节点等与下一个父节点,大致想象为爷爷节点。

5.向下调整(重点)

void AdjustDown(HPDataType *a,int size,int parent)
{
	assert(a);
	int child = parent*2+1;
	while (child < size)
	{
		if (child + 1 < size && a[child] > a[child + 1])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

顾名思义 向下调整就是以开头第一个元素为始,开始依次向子节点比较,当child 大于或等于size时循环停止,child + 1小于size 和 a【child】 大于 a【child + 1】条件的原因是,因为向下调整要对比的是两个子节点,通过比较 选出较小的节点(小堆),如果 【child+1】较小就++child。如果父节点比最小的子节点大,那就交换二者的位置,然后向下以这个逻辑,循环到如果出现 最小的孩子 比父亲节点还大的话,那就break循环,如果没有就循环到child大于等于size为止。?

6.插入(重点)

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : 2 * hp->capacity;
		HPDataType* tmp = (HPDataType*)realloc(hp->a,sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUP(hp->a,hp->size);
}

?对于堆的插入呢,当然首先也是尾插,因为这是一个小堆,如果你插入一个特别小的数,那么这个堆就得重新开始调整了。当然调整就用一个向上调整即可,从最下面往上面调整。

因为是插入,所以要先判断整个数列的空间和现在的元素个数,如果 相等了那就得扩容了。

扩容好以后,把要插入的数字尾插在数列的尾端,同时size++,然后对这个数字进行向上调整。

7.删除(重点)

void HeapPop(HP* hp)
{
	assert(hp);
	Swap(&(hp->a[hp->size]), &(hp->a[0]));
	hp->size--;
	AdjustDown(hp->a,hp->size,0);
}

堆的删除,不是尾删 。而是把头元素删除。?

所以一般的堆删除就是把头尾交换,在把size-- 和顺序的删除很像,就是删除的头结点。、

删除之后对堆在进行一次向下调整即可。因为传上来的数字本来就是在最下面的,所以要把它在沉到最下面。

8.头元素

HPDataType HeapTop(HP* hp)
{
	assert(hp);
	return hp->a[0];
}

9.元素个数

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

10.判空

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

3.堆的排序。

所谓排序,相信大家都已经学过冒泡排序了把,排序就是把一串数字排成升序或者降序。

那我们为什么要学习排序呢?最重要的一点就是?? 面试? ?sdad?

在笔试的时候,最主要的就是靠算法题。像拼多多、头条这种大公司,上来就来几道算法题,如果你没AC出来,面试机会都没有。

在面试(现场面或者视频面)的时候也会问算法题,难度肯定是没有笔试的时候那么难的。我们可以想象一个场景,一面面试面到一半,面试官让你反转二叉树,问问现在的自己,你还会吗。

?所以这些排序我们都还得学,当然以后如果有这方面的工作也会用得到,技多不压身。

堆排序的源代码和实现

#include"Heap.h"
void HeapSort(int* a, size_t size)
{
	for (int i = (size-1-1)/2; i >=0; i--)
	{
		AdjustDown(a, size,i);
	}
	for (int i = size-1; i > 0; i--)
	{
		Swap(&a[i], &a[0]);
		AdjustDown(a, i,0);
	}
}
int main()
{
	int arr[] = { 4,10,22,3,6,9,25,11,715 };
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));
	return 0;
}

首先堆排序咱有两步,第一步是先把一组数组先把它先建立成堆。

第二步就是用调整的方法把这个数组变成有序的

关于建堆有两种方法,第一种是用向上调整直接从数组第一个开始,每一个都进行一次向上调整,如果这样调整的话,建堆这个过程的时间复杂度就是n * logn。

而向下调整建堆的时间复杂度则到达了 n ,快了很多,这是向下调整的图片

?而我们用向下调整建堆呢,是从这个图元素大小为28的最后一个元素的父节点来进行调整的,这种建堆的关键就是从倒数第一个非叶子节点开始调(也就是树中最后一个父节点),然后逐渐+1,就可以调整从最后一个父节点开始的每一棵树.公式里的第一个size - 1呢是因为本来size是计算元素个数的,数组又是从0开始排序的,所以size - 1是要得到最后一个叶子结点。

而第二个 - 1呢是因为,parent = (child - 1)/ 2.因为adjustdown中传入的第三个变量是parent 所以 需要第二次 - 1.(所以一般建堆都是用向下调整建堆,时间效率高)

文章来源:https://blog.csdn.net/a1275174052/article/details/134839366
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。