二叉树顺序结构——堆的结构与实现

时间：2024-06-11 07:03:30

二叉树顺序结构——堆的结构与实现

  • 一、二叉树的顺序结构
  • 二、堆的概念及结构
  • 三、堆的实现
    • 堆向下调整算法
    • 堆的创建
    • 建堆时间复杂度
    • 堆的插入(堆向上调整算法)
    • 堆的删除
    • 堆的代码实现(使用VS2022的C语言)
      • 初始化、销毁
      • 构建、插入、删除
      • 返回堆顶元素、判空、返回有效元素个数
  • 四、完整 Heap.c 源代码

一、二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。
在这里插入图片描述在这里插入图片描述

二、堆的概念及结构

如果有一个关键码的集合K = { k0，k1 ，k2 ，…，k(n - 1) }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： Ki <= K(2 * i +1) 且 Ki <= K(2 * i + 2) (Ki >= K(2 * i + 1) 且 Ki >= K(2 * i + 2) ) ，i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆的性质：

  1. 堆中某个结点的值总是不大于或不小于其父结点的值；
  2. 堆总是一棵完全二叉树。
    在这里插入图片描述
    在这里插入图片描述

三、堆的实现

注意：

  1. 对于堆中父亲节点下标 i ，它的左孩子总是 i * 2 + 1，右孩子总是 i * 2 + 2;
  2. 对于左右孩子节点 i ，由于整数相除会取整，则它们共同的父亲节点为：(i - 1) / 2;
/*
* leftChild = parent * 2 + 1;
* rightChild = parent * 2 + 2;
* parent = (leftChild - 1) / 2 = (rightChild - 1) / 2;
*/

堆向下调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
在这里插入图片描述
在这里插入图片描述

void swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

// 向下调整代码
void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);
	
	// 先找到左孩子
	int child = parent * 2 + 1;
	while (child < n)						// 当child 超过范围退出
	{
		// 假设法
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			++child;
		}
		
		// 若不符合堆的性质，则调整，反之退出
		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;							// 满足堆的性质，直接退出
		}
	}
}

堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根结点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子结点的子树开始调整，一直调整到根结点的树，就可以调整成堆。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

// 堆的创建
void HeapCreate(pHeap ph, HPDataType* arr, int sz)
{
	assert(ph);
	assert(HeapEmpty(ph));		// 堆不为空则不能创建

	HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * sz);
	if (temp == NULL)
	{
		perror("realloc failed");
		return;
	}
	ph->arr = temp;
	ph->size = sz;
	ph->capacity = sz;

	memcpy(ph->arr, arr, sizeof(HPDataType) * sz);
	
	// 倒数的第一个非叶子结点的子树下标为: 
	// (总长 - 2) / 2 == 总长 / 2 - 1
	// 因为对于最后一个叶子节点，它的下标为：
	// 总长 - 1
	// 而我们知道非根节点无论是左右孩子，因为整数用除会取整，
	// 则它的父亲节点均为：
	// (child - 1) / 2
	// 即：
	// lastChild = 总长 - 1;
	// 倒数的第一个非叶子结点的子树下标 = (lastChild - 1) / 2;
	// 得 (总长 - 1 - 1) / 2 == 总长 / 2 - 1
	for (int i = sz / 2 - 1; i >= 0; --i)
	{
		AdjustDown(ph->arr, sz, i);
	}
}

建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个结点不影响最终结果)：
在这里插入图片描述
因此：建堆的时间复杂度为O(N)。

堆的插入(堆向上调整算法)

先插入一个 10 到数组的尾上，再进行向上调整算法，直到满足堆。
在这里插入图片描述

// 向上调整
void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while (child > 0)				// 当 child 为根节点时退出
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;					// 当数据满足堆的性质时退出
		}
	}
}

堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
在这里插入图片描述

堆的代码实现(使用VS2022的C语言)

堆常用的接口包括：

  1. 初始化、销毁

  2. 构建、插入、删除

  3. 返回堆顶元素、判空、返回有效元素个数

在 Heap.h 中：

#pragma once

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

// 初始化容量
#define INIT_CAPACITY 4

// 增容倍率
#define EXPANSION_MULTIPLE 2

typedef int HPDataType;

typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
} Heap, * pHeap;

// 初始化、销毁
void HeapInit(pHeap ph);

void HeapDestroy(pHeap ph);

// 构建、插入、删除
void HeapCreate(pHeap ph, HPDataType* arr, int sz);

void HeapPush(pHeap ph, HPDataType x);

void HeapPop(pHeap ph);

// 返回堆顶元素、判空、返回有效元素个数
HPDataType HeapTop(pHeap ph);

bool HeapEmpty(pHeap ph);

int HeapSize(pHeap ph);

在 Heap.c 中：

初始化、销毁

void HeapInit(pHeap ph)
{
	assert(ph);

	ph->arr = NULL;
	ph->size = 0;
	ph->capacity = 0;
}

void HeapDestroy(pHeap ph)
{
	assert(ph);

	free(ph->arr);
	ph->size = 0;
	ph->capacity = 0;
}

构建、插入、删除

// 堆的创建
void HeapCreate(pHeap ph, HPDataType* arr, int sz)
{
	assert(ph);
	assert(HeapEmpty(ph));		// 堆不为空则不能创建

	HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * sz);
	if (temp == NULL)
	{
		perror("realloc failed");
		return;
	}
	ph->arr = temp;
	ph->size = sz;
	ph->capacity = sz;

	memcpy(ph->arr, arr, sizeof(HPDataType) * sz);

	// 倒数的第一个非叶子结点的子树下标为: 
	// (总长 - 2) / 2 == 总长 / 2 - 1
	// 因为对于最后一个叶子节点，它的下标为：
	// 总长 - 1
	// 而我们知道非根节点无论是左右孩子，因为整数用除会取整，
	// 则它的父亲节点均为：
	// (child - 1) / 2
	// 即：
	// lastChild = 总长 - 1;
	// 倒数的第一个非叶子结点的子树下标 = (lastChild - 1) / 2;
	// 得 (总长 - 1 - 1) / 2 == 总长 / 2 - 1
	for (int i = sz / 2 - 1; i >= 0; --i)
	{
		AdjustDown(ph->arr, sz, i);
	}
}

void HeapPush(pHeap ph, HPDataType x)
{
	assert(ph);
	
	// 先判断空间是否充足
	if (ph->size == ph->capacity)
	{
		int newCapacity = ph->capacity == 0 ? INIT_CAPACITY : ph->capacity * EXPANSION_MULTIPLE;
		HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * newCapacity);
		if (temp == NULL)
		{
			perror("realloc failed");
			return;
		}

		ph->arr = temp;
		ph->capacity = newCapacity;
	}

	ph->arr[ph->size++] = x;
	AdjustUp(ph->arr, ph->size - 1);
}

void HeapPop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	--ph->size;
	swap(&ph->arr[0], &ph->arr[ph->size]);
	AdjustDown(ph->arr, ph->size, 0);
}

返回堆顶元素、判空、返回有效元素个数

HPDataType HeapTop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	return ph->arr[0];
}

bool HeapEmpty(pHeap ph)
{
	assert(ph);

	return ph->size == 0;
}

int HeapSize(pHeap ph)
{
	assert(ph);

	return ph->size;
}

四、完整 Heap.c 源代码

#include "Heap.h"

void HeapInit(pHeap ph)
{
	assert(ph);

	ph->arr = NULL;
	ph->size = 0;
	ph->capacity = 0;
}

void HeapDestroy(pHeap ph)
{
	assert(ph);

	free(ph->arr);
	ph->size = 0;
	ph->capacity = 0;
}

void swap(HPDataType* a, HPDataType* b)
{
	HPDataType temp = *a;
	*a = *b;
	*b = temp;
}

// 向下调整代码
void AdjustDown(HPDataType* arr, int n, int parent)
{
	assert(arr);

	// 先找到左孩子
	int child = parent * 2 + 1;
	while (child < n)						// 当child 超过范围退出
	{
		// 假设法
		if (child + 1 < n && arr[child] > arr[child + 1])
		{
			++child;
		}

		// 若不符合堆的性质，则调整，反之退出
		if (arr[parent] > arr[child])
		{
			swap(&arr[parent], &arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;							// 满足堆的性质，直接退出
		}
	}
}

// 向上调整
void AdjustUp(HPDataType* arr, int child)
{
	assert(arr);

	int parent = (child - 1) / 2;
	while (child > 0)				// 当 child 为根节点时退出
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;					// 当数据满足堆的性质时退出
		}
	}
}

// 堆的创建
void HeapCreate(pHeap ph, HPDataType* arr, int sz)
{
	assert(ph);
	assert(HeapEmpty(ph));		// 堆不为空则不能创建

	HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * sz);
	if (temp == NULL)
	{
		perror("realloc failed");
		return;
	}
	ph->arr = temp;
	ph->size = sz;
	ph->capacity = sz;

	memcpy(ph->arr, arr, sizeof(HPDataType) * sz);

	// 倒数的第一个非叶子结点的子树下标为: 
	// (总长 - 2) / 2 == 总长 / 2 - 1
	// 因为对于最后一个叶子节点，它的下标为：
	// 总长 - 1
	// 而我们知道非根节点无论是左右孩子，因为整数用除会取整，
	// 则它的父亲节点均为：
	// (child - 1) / 2
	// 即：
	// lastChild = 总长 - 1;
	// 倒数的第一个非叶子结点的子树下标 = (lastChild - 1) / 2;
	// 得 (总长 - 1 - 1) / 2 == 总长 / 2 - 1
	for (int i = sz / 2 - 1; i >= 0; --i)
	{
		AdjustDown(ph->arr, sz, i);
	}
}

void HeapPush(pHeap ph, HPDataType x)
{
	assert(ph);

	// 先判断空间是否充足
	if (ph->size == ph->capacity)
	{
		int newCapacity = ph->capacity == 0 ? INIT_CAPACITY : ph->capacity * EXPANSION_MULTIPLE;
		HPDataType* temp = (HPDataType*)realloc(ph->arr, sizeof(HPDataType) * newCapacity);
		if (temp == NULL)
		{
			perror("realloc failed");
			return;
		}

		ph->arr = temp;
		ph->capacity = newCapacity;
	}

	ph->arr[ph->size++] = x;
	AdjustUp(ph->arr, ph->size - 1);
}

void HeapPop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	--ph->size;
	swap(&ph->arr[0], &ph->arr[ph->size]);
	AdjustDown(ph->arr, ph->size, 0);
}

HPDataType HeapTop(pHeap ph)
{
	assert(ph);
	assert(!HeapEmpty(ph));

	return ph->arr[0];
}

bool HeapEmpty(pHeap ph)
{
	assert(ph);

	return ph->size == 0;
}

int HeapSize(pHeap ph)
{
	assert(ph);

	return ph->size;
}

相关文章