堆及其堆排序

admin • 2023-04-12 19:10 • C/C++

堆是一种特殊的数据结构，底层实现是靠数组存储以及完全二叉树的性质

文章目录

一、堆概念
二、堆实现
三、堆源码
四、堆排序

一、堆概念

完全二叉树用数组来存储可以达到空间的有效利用且可以直观反映它们之间的逻辑关系，双亲与孩子之间的关系。一般在数组中都是从0开始，这里存储完全二叉树根也从0开始，那么它们之间父子下标关系：

双亲：prent = (child - 1)/2

左孩子：lchild = parent*2 + 1

右孩子：rchild = parent*2 + 2

用数组存储的值可以将其想象为一棵二叉树，想象出来的二叉树再加以限制就可以得到堆。这棵树中每个父亲节点的值都要大于或者等于它的孩子节点；或者每个父亲节点的值都小于或者等于它的孩子节点；且这棵树是一棵完全二叉树大于或者等于孩子节点的完全二叉树称作大堆，小于或者等于孩子节点的完全二叉树称作小堆

小堆

大堆

堆在逻辑上也是一棵完全二叉树

而大堆的堆顶根是整棵树中最大的，小堆的堆顶根是整棵树中最小的，大堆和小堆是可以快速选出最大值或者最小值

而堆也是基于数组和完全二叉树来实现的数据结构，堆不仅仅可以存储数据，也可以用来对数据进行排序。
堆既然是一种数据结构那么也可以对其进行插入数据和删除数据，但是在插入数据之后还有保证其是堆，所以插入后也要对其调整。而堆是依靠于数组实现的，而数组插入数据在尾部插入最为高效，所以每次在数组尾部插入数据，但是在插入数据后空间就有可能会不够，那么当空间不够时就要考虑扩容，因此就要用动态数组实现堆，静态数组空间给小了可能空间不够，给大了可能会浪费空间

在每一次插入数据时要保证还是大堆或者小堆，那么插入的这个值要与它的父亲比较，如果待插入的值比父亲大，那么就与父亲值交换，如果比父亲值小，则保持不动

而在数组中的插入我们要将其想象为是对一棵完全二叉树进行调整，每次插入有可能都会对这棵树调整，但是这种调整只会影响孩子它的祖先，这种对于这棵树从下面往根调整的方法被称为向上调整算法而向上调整最多调整二叉树的高度次 logⁿ

而小根堆也是一样，每次插入当孩子比父亲小，将其两个交换，再往上一层比较，遇见比其小或者到达树根就停不再调整

二、堆实现

堆存储结构

typedef int HDataType;
typedef struct Heap
{
	HDataType* a;
	int size;
	int capacity;
}Heap;

初始化堆

void HeapInit(Heap* php)
{
	assert(php);
	php->a = (HDataType*)malloc(sizeof(HDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}

		php->size = 0;//初始时没有元素
		php->capacity = 4;//初始容量为4
}

由于后边堆的插入和删除都会交换数据在此写一个交换接口

void Swap(HDataType* e1, HDataType* e2)
{
	HDataType tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

堆插入数据
以大堆为例。在插入数据时要保证为堆，那么就要对其向上调整
向上调整

在数组尾部插入数据，插入的这个数据要与其父亲比较，比父亲大，它们要交换，且孩子下标与父亲下标都要发生改变它们都往上一层走。孩子下标child = parent父亲下标parent = (child - 1) / 2;直到孩子小于父亲或者孩子走到了树根停止

//向上调整算法
//大根堆
void AdjustUp(HDataType* a, int n)
{
	int child = n;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])//如果要建小堆只需要将  '>'改为'<'
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}

		else
		{
			break;
		}
	}
}

//每次插入一个就对其进行向上调整使其成为堆
void HeapPush(Heap* php, HDataType x)
{
	assert(php);
	//扩容
	if (php->size == php->capacity)
	{
		HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		
			php->a = tmp;
			php->capacity *= 2;
	}
   
	php->a[php->size] = x;//插入数据

	AdjustUp(php->a, php->size);//调整使其还是堆
	php->size++;
}

堆删除数据

堆通过插入数据将其建成了一个大堆，堆顶也就是最大的了，那么我们在对对的数据进行删除时应该删除堆顶还是堆尾，如果是删除最后一个的话那么可以很轻松删除，直接将数组长度减一就可，但是这没有很大的意义。有一句话叫做擒贼先擒王，将最大的做掉然后老二才能上来，而且堆不仅仅是存储数据，既可以实现选数据也可以实现排序，选数据选出最大的前k个或者最小的前k个，因此在堆删除数据时，删除堆顶可以很轻松选出堆中前k个数据，但是在直接删除堆顶时，在逻辑上不再是一棵树了

因此有一种很妙的方法先将堆最后一个与堆顶交换，然后再删除堆中最后一个元素

但是交换并删除后不再是堆了，我们需要将其再次调整为堆，由于交换的是堆顶和堆尾，只动了这两个元素，那么堆中其它位置元素没有发生改变也就是其它位置还是堆，而这时交换过后树不一定是堆，但是除了树根之外其余的子树都还是堆，这时需要从树根对其调整，这种调整也叫做向下调整算法

调整到叶子或者遇见孩子比它小的就不会再调
向下调整

向下调整最坏的调整次数为高度次logⁿ

//向下调整算法是基于根的左右子树都是大根堆或者小根堆的前提下
// 由于在插入数据是就已经将堆调整为大根堆了，因此在删除时将根与最后一个数据交换，然后再队整个树进行向下调整
// 但是除了根之外其他的子树都已经是大根堆了，因此就好调整了
//原本它的左右子树已经是大根堆了
void AdjustDown(HDataType* a,int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;//默认左孩子值较大
	while (child < n)
	{
		if (child+1<n&& a[child] < a[child + 1])//这两个判断条件位置不可改变，先判断值可能会导致非法访问
		{
			child++;
		}

		//调整时注意极端情况，调到叶子节点，且右孩子大于左孩子但是这时的右孩子是不在数组范围内的，那么这时如果孩子大于父亲值，那么就会交换
		//会导致出现随机值,因此要保证它的左孩子节点和右孩子节点是在数组长度范围内
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}

		else
		{
			break;
		}
	}
}

判断堆空

bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

而将堆顶数据删除之后

//堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));//删空
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size,0);//调整范围变为堆删除数据后的大小
	
}

获取堆顶元素

//获取堆根
HDataType HeapTop(Heap* php)
{
	assert(php);
	//assert(!HeapEmpty(php));
	return php->a[0];
}

堆大小

//获取堆大小
int HeapSize(Heap* php)
{
	return php->size;
}

销毁堆

//销毁堆
void HeapDestroy(Heap* php)
{
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

三、堆源码

Heap.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int HDataType;
typedef struct Heap
{
	HDataType* a;
	int size;
	int capacity;
}Heap;

void HeapInit(Heap* php);
void HeapPush(Heap* php, HDataType x);
void HeapDestroy(Heap* php);
bool HeapEmpty(Heap* php);
void HeapPop(Heap* php);
int HeapSize(Heap* php);
HDataType HeapTop(Heap* php);
int HeapSize(Heap* php);

heap.c

#include"Heap.h"
//初始话堆
void HeapInit(Heap* php)
{
	assert(php);
	php->a = (HDataType*)malloc(sizeof(HDataType) * 4);
	if (php->a == NULL)
	{
		perror("malloc fail");
		return;
	}

	else
	{
		php->size = 0;
		php->capacity = 4;
	}
}

void Swap(HDataType* e1, HDataType* e2)
{
	HDataType tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}
//向上调整算法
//大根堆
void AdjustUp(HDataType* a, int n)
{
	int child = n;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}

		else
		{
			break;
		}
	}
}

void HeapPush(Heap* php, HDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		HDataType* tmp = (HDataType*)realloc(php->a, sizeof(HDataType) * php->capacity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}


		php->a = tmp;
		php->capacity *= 2;


	}

	php->a[php->size] = x;
	AdjustUp(php->a, php->size);
	php->size++;
}


void AdjustDown(HDataType* a, int n, int root)
{
	int parent = root;
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}

		else
		{
			break;
		}
	}
}

//堆的删除
void HeapPop(Heap* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);

	AdjustDown(php->a, php->size - 1, 0);
	php->size--;
}//判空
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

//获取堆根
HDataType HeapTop(Heap* php)
{
	assert(php);
	//assert(!HeapEmpty(php));
	return php->a[php->size];
}

//获取堆大小
int HeapSize(Heap* php)
{
	return php->size;
}

//销毁堆
void HeapDestroy(Heap* php)
{
	free(php->a);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

test.c

#include"Heap.h"

//
void test()
{
	Heap php;
	HeapInit(&php);
	HeapPush(&php, 2);
	HeapPush(&php, 3);
	HeapPush(&php, 4);
	HeapPush(&php, 10);
	///*int k = 0;
	//k = 3;
	while (!HeapEmpty(&php))
	{
		HeapPop(&php);
		printf("%d ", HeapTop(&php));
		;
	}
  // HeapPop(&php);
	/*printf("%d ", HeapTop(&php));
	
	HeapPop(&php);
	printf("%d ", HeapTop(&php));
	HeapPop(&php);
	printf("%d ", HeapTop(&php));
	HeapPop(&php);
	printf("%d ", HeapTop(&php));
	HeapPop(&php);
	printf("%d ", HeapTop(&php));*/
}

int main()
{
	test();
	return 0;
}

四、堆排序

堆如何做到排序的？

堆排序可以借助堆这个数据结构，但是如果是在学校考试的时候你要手搓一个堆结构吗，这时耗费大量时间等你写好一个堆考试都结束了。而且其空间复杂度为O(N),由于将数组内容插入到堆中去，而堆内部是需要开空间的。

因此堆排序可以脱离堆这个结构。对数组进行排序，我们可以将数组看作一个完全二叉树，但是完全二叉树不一定是堆，而可以将这棵完全二叉树建成堆，可以向上调整建堆（模拟堆插入过程）将整个数组看作是堆里面的，然后从第一个数开始向上调

向上调整建堆

//向上建堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

向上调整大堆已经建成，也就是模拟堆插入的过程，向上调整建堆时间复杂度为nlogⁿ

也可以向下调整建堆

向下调整建堆不能从根就开始调，因为不一定满足它的左右子树都是大堆或者小堆，向下调整要满足左右子树是大堆或者小堆。从数组首元素不行，那么有人想到了从数组末尾开始向下调整，也就是完全二叉树的叶子去调，但是叶子只有一个无意义，那么从最后一个叶子它的父亲开始调，然后调好之后依次往前调，从后往前跳可以保证它的左右子树都是堆，倒着来调整

for (int i = (n - 1-1) / 2; i >= 0; i--)
	{
		//那么这里就从数组下标末尾开始向上调
		AdjustDown(a, n, i);
	}

堆已经建好，那么堆排序排升序是建大堆还是小堆，建大堆，排降序建小堆。

升序：因为堆顶是最大或者最小的，大堆每一次可以得出最大的那个数，让堆顶元素和最后一个交换，然后再缩小调整范围，这时堆的最后一个元素不参与调整，然后让0~n-1调整，每调整一次就会将堆中最大的数弄到最后，然后它又不参与调整了，每一次调整范围减一，最后就将数据排为升序的了

降序：建小堆，堆顶为最小，堆顶与最后一个交换可以将最小值交换到最后，得到堆中最小值，这时交换后的最小值不再参与堆调整的过程，然后调整堆，每次交换后堆的调整范围都会缩小一个，直到最后将这些数据排为降序了

向上调整与向下调整时间复杂度比较
向上调整nlogⁿ
向下调整logⁿ

向上调整算法时间复杂度nlog^n

向下调整时间复杂度为N因此建堆时采用向下调整算法较好

这时堆排序已成，
堆排序源码

#include<stdio.h>

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

//向下调整算法
void AdjustDown(int* a, int n,int root)
{
	int parent = root;
	int child = parent * 2 + 1;

	while (child < n)
	{

		if (child+1<n&&a[child + 1] > a[child])//如果右孩子要大于左孩子
		{
          //孩子节点就会变为右孩子
			child += 1;
		}
   
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2+1;
		}

		else
		{
			break;
		}
	}
}


void AdjustUp(int* a, int n)
{
	int child = n;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])//如果要建小堆只需要将  '>'改为'<'
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}

		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	
	//向上调整建堆
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	/*
   

	//向下调整建堆
	/*for (int i = (n - 1-1) / 2; i >= 0; i--)
	{
		那么这里就从数组下标末尾开始向上调
		AdjustDown(a, n, i);
	}*/

	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
		
	}
}
 

void TestHeapSort()
{
	int arr[] = { 6,7,8,9,1,2,3,4,5,6,7,8,9 };
	HeapSort(arr, sizeof(arr) / sizeof(arr[0]));

	for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
	{
		printf("%d ", arr[i]);
	}
}

int main()
{
	TestHeapSort();
	return 0;
}

堆排序时间复杂度为Nlog^N

堆可以实现得到很多数据中前k个最大值或者最小值，在选数中及其重要

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

c语言排序算法数据结构

二维码

什么是堆，如何实现？(附堆排序，TOP-K问题)

< <上一篇

【linux】：进程地址空间

下一篇>>

搜索内容