数据结构 | 详解二叉树—

数据结构 | 详解二叉树——堆与堆排序

🥝堆

堆总是一棵完全二叉树。

大堆：父节点总是大于子节点。

小堆：父节点总是小于子节点。

注意：1.同一个节点下的两个子节点并无要求先后顺序。

2.堆可以是无序的。

🍉堆的实现

🌴深度剖析

1.父节点和子节点之间的关系

子节点=（父节点*2）+1

或者子节点=（父节点*2）+2

父节点=（子节点-1）/2

2.堆的插入HeapPush实现

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

void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->size == php->capacity) {int newcapacity = 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("malloc fail!");}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;AdjustUp(php->a,php->size);php->size++;
}

3.堆的删除HeapPop函数的实现

函数目的：删除堆顶元素

为了避免破坏堆的整体结构，先将首尾元素进行交换，再对首元素进行向下调整，直到满足堆。最后php->size--即可删除原栈顶元素。

void HeapPop(Heap* php) {assert(php);swap(&php->a[0], &php->a[php->size - 1]);AdjustDown(php->a, php->size,0);php->size--;
}

🥳代码实现

Heap.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;void HeapInit(Heap* php);
// 堆的销毁
void HeapDestory(Heap* php);
// 堆的插入
void HeapPush(Heap* php, HPDataType x);
// 堆的删除
void HeapPop(Heap* php);
// 取堆顶的数据
HPDataType HeapTop(Heap* php);
// 堆的数据个数
int HeapSize(Heap* php);
// 堆的判空
int HeapEmpty(Heap* php);

Heap.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
void HeapInit(Heap* php) {assert(php);php->a = NULL;php->capacity = php->size = 0;
}void HeapDestory(Heap* php) {assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}void swap(int* a, int* b) {int tmp = *a;*a= *b;*b = tmp;
}
//小堆
void AdjustUp(HPDataType* a,int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[parent] > a[child]) {swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}void HeapPush(Heap* php, HPDataType x) {assert(php);if (php->size == php->capacity) {int newcapacity = 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType) * newcapacity);if (tmp == NULL) {perror("malloc fail!");}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;AdjustUp(php->a,php->size);php->size++;
}
//从给定的子节点开始，不断向上与其父节点进行比较和可能的交换，直到达到根节点或找到一个满足最大堆性质的父节点为止。
void AdjustDown(int* a, int n, int parent) {assert(a);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);swap(&php->a[0], &php->a[php->size - 1]);AdjustDown(php->a, php->size,0);php->size--;
}HPDataType HeapTop(Heap* php) {assert(php);assert(php->size > 0);return php->a[0];
}int HeapSize(Heap* php) {assert(php);return php->size;
}int HeapEmpty(Heap* php) {assert(php);return php->size;
}

test.c

#define _CRT_SECURE_NO_WARNINGS
#include "Heap.h"
int main() {Heap hp;HeapInit(&hp);HeapPush(&hp, 7);HeapPush(&hp, 6);HeapPush(&hp, 5);HeapPush(&hp, 4);HeapPush(&hp, 3);HeapPush(&hp, 2);HeapPush(&hp, 1);for (int i = 0; i < hp.size; i++) {printf("%d ", hp.a[i]);}HeapPop(&hp);printf("\n");for (int i = 0; i < hp.size; i++) {printf("%d ", hp.a[i]);}printf("\n");printf("堆顶元素为%d\n", HeapTop(&hp));if (HeapEmpty(&hp)) {printf("堆不为空\n");}else {printf("堆为空\n");}return 0;
}

🍇堆排序

🌴深度剖析

第一步：建堆

（升序建大堆，降序建小堆）

以升序为例：

从最后一个父节点开始向前遍历，向上调整(大的上小的下）。

	//建堆：从倒数第一个父节点开始向前遍历，向下调整for (int i = (n-1-1)/2; i >=0 ;i--) {AdjustDown(a,n,i);}

第二步：排序

1.首尾元素交换（左图）

2.再向下调整（大的上小的下），这样调整后的堆顶元素必为调整范围内的最大值，经过下一轮的首尾元素交换后，就可以放入调整完的区域内。

while (n - 1) {swap(&a[0], &a[n - 1]);AdjustDown(a, n-1,0);n--;

🥳代码实现

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>void swap(int* a, int* b) {int tmp = *a;*a = *b;*b = tmp;
}void AdjustUp(int* a, int child) {assert(a);int parent = (child - 1) / 2;while (child > 0) {if (a[parent] < a[child]) {swap(&a[parent], &a[child]);child = parent;parent = (child - 1) / 2;}else {break;}}
}
void AdjustDown(int* a, int n, int parent) {assert(a);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 HeapSort(int* a, int n) {//建堆：从倒数第一个父节点开始向前遍历，向下调整for (int i = (n-1-1)/2; i >=0 ;i--) {AdjustDown(a,n,i);}//先将首尾元素进行交换，再向下调整while (n - 1) {swap(&a[0], &a[n - 1]);AdjustDown(a, n-1,0);n--;}
}int main() {int a[7] = { 2,6,5,1,7,4,3 };int n = sizeof(a) / sizeof(a[0]);HeapSort(a, n);for (int i = 0; i < n; i++) {printf("%d ",a[i]);}return 0;
}