当前位置：首页 > article >正文

《二叉树：二叉树的顺序结构-＞堆》

article 2026/2/11 17:34:17

二叉树一般可以使用两种结构存储，一种是顺序结构，一种是链式结构。

顺序存储

顺序结构存储是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。实际上使用中只有堆才会使用数组来存储。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

链式存储

用链表来表示一颗二叉树。使用链来指示元素的逻辑关系。链表中每个节点由三个域组成，数据域和左右指针，左右指针分别指向该结点的左孩子和右孩子所在链结点的存储地址。链式结构又分为二叉链和三叉链。本篇内容为二叉链。

二叉树的顺序结构实现

把堆（完全二叉树）使用顺序结构的数组来存储。

大根堆：树中的每个结点，其值都大于或等于其子结点的值。也就是说，在大根堆中，根结点是堆中的最大元素。

小根堆：树中的每个结点，其值都小于或等于其子结点的值。也就是说，在小根堆中，根结点是堆中的最小元素。

堆的性质

堆中某个结点的值总是不大于或不小于其父结点的值
堆总是一颗完全二叉树

堆的实现

下面所演示的为一个小堆的实现。

向下调整算法

给出一个数组，逻辑上看作是一颗完全二叉树。通过根结点的向下调整算法可以把它调整为一个小堆/大堆。向下调整算法有一个前提：左右子树必须是一个小堆/大堆，才可以调整。

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

下面我们演示一下小堆的向下调整算法。

// 小堆向下调整算法 
// 注意：调整的树的左右子树必须为小堆
void AdjustDown(HPDataType* a, int n, int root)
{// 父亲int parent = root;// 1.选出左右孩子较小的孩子跟父亲比较// 默认较小的孩子为左孩子int child = parent * 2 + 1;// 终止条件孩子到叶子结点最后跟父亲比一次while (child < n){// 2.如果右孩子小于左孩子，则较小的孩子为右孩子 if (child + 1 < n && a[child + 1] < a[child]){child++;}// 3.如果孩子小于父亲，则跟父亲交换if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

向下调整算法时间复杂度为O（log（N））。

堆的创建

通过向下调整算法，可以构建一个小堆，但是前提是根的左右子树本来就为小堆。但是如果根结点的左右子树不为小堆，怎么调整呢？

从最后一个非叶子结点开始向下调整，一直调整到根，就能构建出一个小堆。最后一个非叶子结点可以看做它的左右子树（叶子结点）就是小堆，所以从这个切入点开始，每次向下调整都能保证左右子树是一个小堆，直到根开始向下调整的时候，它的左右子树此时就已经为一个小堆了。

下面来演示一下这个过程。

void HeapInit(Heap* php,HPDataType* a,int n)
{php->_capacity = n;php->_size = n;php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->_a == NULL){perror("HeapInit");return;}memcpy(php->_a, a, sizeof(HPDataType)*n);// 创建小堆// 最后一个非叶子结点下标为（n-1-1）/2for (int i = (n - 1 - 1) / 2; i >= 0; i--){// 从最后一个非叶子结点开始向下调整，一直调整到根，就能保证构建出来的堆是一个小堆AdjustDown(php->_a, php->_size, i);}
}

建堆的时间复杂度

O（N）。

堆的插入

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

向上调整算法

将元素插入到堆的末尾
插入之后如果堆结构被破坏，将插入的新结点顺着其双亲向上调整到合适的位置即可。

// 向上调整算法 
void AdjustUp(HPDataType* a, int n,int child)
{assert(a);// 父亲和孩子的关系：parent=（child-1）/2int parent = (child - 1) / 2;// while(parent >= 0)  error，如果最后调整的是根，parent =（1-1）/2=0 条件依然满足，parent = （0-1）/2=0 无限循环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, HPDataType x)
{assert(php);if (php->_capacity == php->_size){php->_capacity *= 2;HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity);if (tmp == NULL){perror("CheckCapacity");return;}php->_a = tmp;}php->_a[php->_size] = x;php->_size++;// 向上调整算法AdjustUp(php->_a, php->_size, php->_size - 1);
}

向上调整算法时间复杂度为O（log（N））

堆的删除

删除堆，是删除堆顶的数据，不能直接将堆顶的数据直接删除，因为一旦直接删除，堆结构就被破坏了。将堆顶的数据与最后一个数据交换，然后删除数组最后一个数据，再进行堆的向下调整即可。

将堆顶元素与堆最后一个元素交换
删除堆最后一个元素
将堆顶元素向下调整直到满足堆特性

// 堆的删除
void HeapPop(Heap* php)
{assert(php);assert(php->_size > 0);// 交换堆顶与最后一个元素Swap(&php->_a[0], &php->_a[php->_size - 1]);php->_size--;// 堆顶元素向下调整AdjustDown(php->_a, php->_size, 0);
}

堆的应用

堆排序

堆排序利用了堆的思想来排序。

1、建堆

排升序，建大堆
排降序，建小堆

2、利用堆删除思想进行排序

建堆和堆删除都使用了堆的向下调整算法，因此，理解了向下调整算法，就掌握了堆排序。

void HeapSort(int* a, int n)
{assert(a);//建堆 排升序 建大堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end >= 1){// 交换堆顶与最后一个元素Swap(&a[0], &a[end]);// 向下调整AdjustDown(a, end, 0);end--;}
}

以排升序为例，建大堆。

堆顶元素是最大的，将堆顶元素与最后一个元素交换，最后一个元素就是最大的元素。

然后堆顶元素再进行向下调整，调整之后，堆顶元素就是除第二大元素，再将堆顶元素与最后倒数第二个元素交换，此时，第二大的元素就在倒数第二个位置了。

以此类推，最后的堆结构就是一个小堆结构，并且是有序的，升序。

堆排序的时间复杂度为：建堆阶段+堆排序阶段时间复杂度=O（N）+O（NlogN）=O（NlogN）

Top-K问题

求数据集合中前K个最大元素或前K个最小元素，一般情况下数据量都比较大。

对于Top-K问题，最先想到的肯定是排序，但是：如果数据量非常大，排序就不太可能了，数据可能不能一下全部都加载到内存中。最好的方式是用堆来解决。

1、用数据集合中前K个元素来建堆。

求前K个最大的元素，则建小堆
求前K个最小的元素，则建大堆

2、用剩余的N-K个元素依次与堆顶元素比较，满足则替换堆顶元素，再进行向下调整。将剩余N-K个元素比较完之后，堆中剩余的就是所求的前K个最大元素或者最小元素。

以求前K个最大元素为例：建小堆，因为小堆的堆顶元素是堆中最小的元素，当后续元素与堆顶元素比较时，如果该元素比堆顶元素大，就可以替换堆顶元素，然后重新调整堆，这样可以保证堆中始终保留当前最大的K个元素。

HPDataType* HeapTopK(Heap* php,int k)
{assert(php);HPDataType* arrk = (HPDataType*)malloc(sizeof(HPDataType) * k);// 前K个元素建堆for (int i = 0; i < k; i++){arrk[i] = php->_a[i];}for (int i = (k-1-1)/2; i >= 0; i--){// 求前K最大元素，向下调整建小堆AdjustDown(arrk, k, i);}// 剩余N-K个数据依次与堆顶比较for (int j = k; j < php->_size; j++){// 如果比堆顶大，则替换，再向下调整if (php->_a[j] > arrk[0]){arrk[0] = php->_a[j];AdjustDown(arrk, k, 0);}}return arrk;
}

全部代码

Heap.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>typedef int HPDataType;typedef struct Heap
{HPDataType* _a;int _size;int _capacity;
}Heap;// 堆初始化
void HeapInit(Heap* php,HPDataType* a,int n );// 向下调整
void AdjustDown(HPDataType* a, int n, int root);// 打印堆
void HeapPrint(Heap* php);// 堆的插入
void HeapPush(Heap* php, HPDataType x);// 堆的删除
void HeapPop(Heap* php);// 取堆顶的数据
HPDataType HeapTop(Heap* php);// 取最大的前k个数据
// 1.堆排序
// 2.HeapPop k-1次
// 3.排升序，建k个元素的小堆
HPDataType* HeapTopK(Heap* php,int k);

Heap.c:

#include"Heap.h"void Swap(HPDataType* p1, HPDataType* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void HeapInit(Heap* php,HPDataType* a,int n)
{php->_capacity = n;php->_size = n;php->_a = (HPDataType*)malloc(sizeof(HPDataType) * n);if (php->_a == NULL){perror("HeapInit");return;}memcpy(php->_a, a, sizeof(HPDataType)*n);// 构建小堆// 最后一个非叶子结点下标为（n-1-1）/2for (int i = (n - 1 - 1) / 2; i >= 0; i--){// 从最后一个非叶子结点开始向下调整，一直调整到根，就能保证构建出来的堆是一个小堆AdjustDown(php->_a, php->_size, i);}
}// 小堆向下调整算法 
// 注意：调整的树的左右子树必须为小堆
void AdjustDown(HPDataType* a, int n, int root)
{// 父亲int parent = root;// 1.选出左右孩子较小的孩子跟父亲比较// 默认较小的孩子为左孩子int child = parent * 2 + 1;// 终止条件孩子到叶子结点最后跟父亲比一次while (child < n){// 2.如果右孩子小于左孩子，则较小的孩子为右孩子 if (child + 1 < n && a[child + 1] < a[child]){child++;}// 3.如果孩子小于父亲，则跟父亲交换if (a[child] < a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}// 向上调整算法 
void AdjustUp(HPDataType* a, int n,int child)
{assert(a);// 父亲和孩子的关系：parent=（child-1）/2int parent = (child - 1) / 2;// while(parent >= 0)  error，如果最后调整的是根，parent =（1-1）/2=0 条件依然满足，parent = （0-1）/2=0 无限循环while (child > 0){if (a[child] < a[parent]){Swap(&a[child], &a[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}void HeapPrint(Heap* php)
{assert(php);for (int i = 0; i < php->_size; i++){printf("%d ", php->_a[i]);}printf("\n");
}void HeapPush(Heap* php, HPDataType x)
{assert(php);if (php->_capacity == php->_size){php->_capacity *= 2;HPDataType* tmp = (HPDataType*)realloc(php->_a, sizeof(HPDataType) * php->_capacity);if (tmp == NULL){perror("CheckCapacity");return;}php->_a = tmp;}php->_a[php->_size] = x;php->_size++;AdjustUp(php->_a, php->_size, php->_size - 1);
}void HeapPop(Heap* php)
{assert(php);assert(php->_size > 0);//交换堆顶与最后一个元素Swap(&php->_a[0], &php->_a[php->_size - 1]);php->_size--;AdjustDown(php->_a, php->_size, 0);
}HPDataType HeapTop(Heap* php)
{assert(php);return php->_a[0];
}HPDataType* HeapTopK(Heap* php,int k)
{assert(php);HPDataType* arrk = (HPDataType*)malloc(sizeof(HPDataType) * k);// 前K个元素建堆for (int i = 0; i < k; i++){arrk[i] = php->_a[i];}for (int i = (k-1-1)/2; i >= 0; i--){// 求前K最大元素，向下调整建小堆AdjustDown(arrk, k, i);}// 剩余N-K个数据依次与堆顶比较for (int j = k; j < php->_size; j++){// 如果比堆顶大，则替换，再向下调整if (php->_a[j] > arrk[0]){arrk[0] = php->_a[j];AdjustDown(arrk, k, 0);}}return arrk;
}

Test.c:

#include"Heap.h"void HeapSort(int* a, int n)
{assert(a);//建堆 排降序 建小堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}int end = n - 1;while (end >= 1){// 交换堆顶与最后一个元素Swap(&a[0], &a[end]);// 向下调整AdjustDown(a, end, 0);end--;}
}int main()
{Heap hp;int arry[] = { 27,15,19,18,28,34,69,49,25,37 };int n = sizeof(arry) / sizeof(arry[0]);HeapInit(&hp,arry,n);HeapPrint(&hp);HeapPush(&hp,20);HeapPrint(&hp);// 堆排序arryHeapSort(arry, n);for (int i = 0; i < n; i++){printf("%d ", arry[i]);}printf("\n");// Top前5个最大的元素int* arrk =HeapTopK(&hp,5);int i = 0;for (i = 0; i < 5; i++){printf("%d ", arrk[i]);}return 0;
}

二叉树的链式结构实现

关于二叉树的链式结构实现可以看下篇文章。

【二叉树进阶】二叉搜索树