数据结构：“大根堆、小根堆”的向上调整算法和向下调整算法

#数据结构：“大根堆、小根堆”的向上调整算法和向下调整算法| 来源: 网络整理| 查看: 265

堆

堆是一种特殊的完全二叉树。堆有两种类型：大根堆和小根堆。在这里插入图片描述

在这里插入图片描述

例1中的完全二叉树符合所有父亲节点的数据小于其孩子节点的，故为小根堆；

例2中的完全二叉树符合所有父亲节点的数据大于其孩子节点的，故为大根堆。

如果给你一个完全二叉树，需要将这个二叉树调整为堆，你会怎么做？这个时候最好的方法便是调整算法。在这里插入图片描述【向上调整算法】

【向下调整算法】与向上调整法有些不一致，这就像一个父亲有两个孩子，过年的时候，如果孩子们想去父亲家，只有一个去处，而换做父亲，该去哪个孩子家过年呢？很多家庭都偏爱小的，所以父亲选择去小儿子家过年。

在向下调整的时候与偏小的孩子节点之间进行调整。

在这里插入图片描述向上调整算法和向下调整算法最能体现在堆的插入和删除

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

【堆的插入】

先将要插入的元素插入到堆的末尾，插入后如果堆的性质被破坏，将新插入的节点顺着其父亲节点往上重新调整为堆。

void AdjustUp(int* a, int child) { assert(a); //父亲节点的下标 int parent = (child - 1) / 2; while (child > 0) { if (a[child] break; } } } void HeapPush(HP* hp, HPDataType x) { assert(hp); if (hp->size == hp->capacity) { //如果容量为0则开四个整形空间，如果不喂0开它原来的两倍 size_t newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2; HPDataType* tmp = realloc(hp->a, sizeof(HPDataType)*newCapacity); if (tmp == NULL) { printf("realloc fail\n"); exit(-1); } hp->a = tmp; hp->capacity = newCapacity; } hp->a[hp->size] = x; hp->size++; //重新调整为堆 AdjustUp(hp->a, hp->size - 1); }

【堆的删除】

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

void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; while (child ++child; } // 如果小的孩子小于父亲，则交换，并继续向下调整 if (a[child] break; } } } // 删除堆顶的数据 void HeapPop(HP* hp) { assert(hp); if（hp->size == 0） { printf("pop fail\n"); exit(-1); } Swap(&hp->a[0], &hp->a[hp->size - 1]); hp->size--; AdjustDown(hp->a, hp->size, 0); }

【本文地址】

公司简介

联系我们