【数据结构】堆（堆的实现堆向下调整算法堆的创建堆的插入堆的删除堆的代码实现堆的应用）

文章目录

- 堆的实现
- - 堆向下调整算法
  - 堆的创建
  - 堆的插入
  - 堆的删除
  - 堆的代码实现
  - 堆的应用

堆的实现

堆是属于操作系统进程地址空间内存区域的划分。

我们下面实现数据结构中的堆。
堆是一个完全二叉树：分为小根堆和大根堆。
小根堆：任何一个节点的值都<=孩子的值
在这里插入图片描述

大根堆：任何一个节点的值都>=孩子的值
在这里插入图片描述

应用：

1.堆排序，第一个时间复杂度达到–O(N*log N)的排序。
2.topK问题：找一堆数据前K大或者前K小。

数组下标计算父子关系公式：

左孩子：leftchild = parent*2 + 1
右孩子：rightchild = parent*2 + 2
孩子算父亲：parent = (child - 1) / 2

堆向下调整算法

给出一个数组，逻辑上看做一颗完全二叉树。通过从根节点开始的向下调整算法可以把它调整成一个小堆。
前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

在这里插入图片描述

堆的创建

给出一个数组，逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们把它构建成一个堆。根节点左右子树不是堆，这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
采用向下调整建堆。

int a[] = {1,5,3,8,7,6};

在这里插入图片描述

堆的插入

先插入一个数组的尾上，再进行向上调整算法，直到满足堆。

1.先将元素插入到对的末尾，即最后一个孩子之后。
2.插入之后如果堆的性质遭到了破坏，将新插入节点顺着双亲往上调整到合适位置即可。
在这里插入图片描述
AdjustUp

堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。

1.将堆顶元素与堆中追后一个元素进行交换。
2.删除堆中最后一个元素
3.将堆顶元素向下调整到满足堆特性为止。

在这里插入图片描述

堆的代码实现

heap.h

#pragma once

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

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HeapPrint(HP* php);

void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);

void HeapInit(HP* php);
void HeapDestroy(HP* php);
// xֶ̬
void HeapPush(HP* php, HPDataType x);
// ɾѶԪ
void HeapPop(HP* php);
// ضѶԪ
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);

Heap.c

#include "Heap.h"

void HeapPrint(HP* php)
{
	for (int i = 0; i < php->size; ++i)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}

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

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->capacity = php->size = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 插入x继续保持堆形态 -- logN
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	// 扩容
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity*sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}

void AdjustDown(HPDataType* a, int n, int parent)
{
	int minChild = parent * 2 + 1;
	while (minChild < n)
	{
		// 找出小的那个孩子
		if (minChild+1 < n && a[minChild + 1] < a[minChild])
		{
			minChild++;
		}

		if (a[minChild] < a[parent])
		{
			Swap(&a[minChild], &a[parent]);
			parent = minChild;
			minChild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// 删除堆顶元素 -- 找次大或者次小 -- logN
// O(logN)
void HeapPop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

// 返回堆顶的元素
HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));

	return php->a[0];
}

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

int HeapSize(HP* php)
{
	assert(php);

	return php->size;
}