数商云是干嘛的,杭州seo首页优化软件,南通优化网站公司哪家好,廊坊购物网站开发设计文章目录 堆的概念堆的实现HeapPushHeapPop HeapTop HeapSize HeapEmpty堆的应用 堆的概念
堆是一颗完全二叉树每个结点的值都小于子结点的值#xff0c;这颗二叉树为小根堆每个结点的值都大于子结点的值#xff0c;这颗二叉树为大根堆堆的定义如下#xff1a;n个元素的序列… 文章目录 堆的概念堆的实现HeapPushHeapPop HeapTop HeapSize HeapEmpty堆的应用 堆的概念
堆是一颗完全二叉树每个结点的值都小于子结点的值这颗二叉树为小根堆每个结点的值都大于子结点的值这颗二叉树为大根堆堆的定义如下n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时称之为堆。 堆的性质堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。
堆的实现
在讲堆的实现前我们首先要知道堆需要实现的功能。
HeapPushHeapPop(删除根结点)HeapTopHeapSizeHeapEmpty 接下来我们要先创建和销毁一个堆。
typedef int HeapType;
typedef struct Heap
{HeapType* arr;int size;int capacity;
}Hp;
void HeapInit(Hp* php)
{assert(php);php-arr NULL;php-capacity php-size 0;
}
void HeapDestroy(Hp* php)
{assert(php);free(php-arr);php-arr NULL;php-capacity php-size 0;
}HeapPush
实现HeapPush时难点在于如何保持整体是一个堆。 即在一个堆的后面插入一个值那么这棵完全二叉树大概率不会是堆那么我们需要将这个值和其父结点比较再根据需要交换值也就是AdjustUp。 那么接下来以小根堆为例实现HeapPush。
void Swap(HeapType* a, HeapType* b)
{HeapType tmp *a;*a *b;*b tmp;
}
void AdjustUp(HeapType* arr, int child)
{int parent (child - 1) / 2;while (child0){if (arr[child] arr[parent]){Swap(arr[child], arr[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
void HeapPush(Hp* php, HeapType x)
{assert(php);if (php-size php-capacity){int newcapacity (php-capacity 0 ? 4 : 2 * php-capacity);HeapType * tmp (HeapType*)realloc(php-arr,newcapacity * sizeof(HeapType));if (!tmp){perror(realloc fail!);exit(-1);}php-arr tmp;php-capacity newcapacity;}php-arr[php-size] x;php-size;AdjustUp(php-arr, php-size - 1);
}HeapPop
实现HeapPop也是和HeapPush一样需要考虑的是如何维持整体完全二叉树是一个堆由于我们删除的是根结点如果将根结点的子结点向上调整那么整体二叉树就会空出一个位置导致变成非完全二叉树。 这里的解决办法是将根结点和最后一个结点交换删除最后一个结点然后再对根结点进行向下调整。
void AdjustDown(HeapType* a, int n, int parent)
{int child 2 * parent 1;while (childn){if (child 1 n a[child] a[child 1]){child;}if (a[parent] a[child]){Swap(a[child], a[parent]);parent child;child 2 * parent - 1;}else{break;}}
}
void HeapPop(Hp* php)
{assert(php);assert(php-size);Swap(php-arr[0], php-arr[php-size - 1]);php-size--;AdjustDown(php-arr, php-size, 0);
}HeapTop HeapSize HeapEmpty
实现了Heap的Push和Pop后那么取根结点的值和判空、判满也是手到擒来的。
HeapType HeapTop(Hp* php)
{assert(php);assert(php-size);return php-arr[0];
}
size_t HeapSize(Hp* php)
{assert(php);return php-size;
}
bool HeapEmpty(Hp* php)
{assert(php);return php-size 0;
}堆的应用
实现了堆那么我们肯定要知道能用在什么地方才行实际上堆的应用也是非常广泛的
实现堆排序求Top K值问题求中位数、百分位数
等等。 堆的应用还有很多这里就不一一赘述了。
