长春教做网站带维护的培训机构,没内涵网站源码,外链的论坛网站,企业网站建设公司制作平台目录 1. 堆的概念和特点2. 堆的实现2.1 堆向下调整算法2.2堆的创建2.3 建堆时间复杂度2.4 堆的插入2.5 堆的删除2.6 堆的代码实现2.6.1 结构体2.6.2 初始化2.6.3 销毁2.6.4 插入2.6.5 删除2.6.6 获取堆顶2.6.7 判空2.6.8 个数2.6.9 向上调整2.6.10 向下调整3. 堆的实现测试测试… 目录 1. 堆的概念和特点2. 堆的实现2.1 堆向下调整算法2.2堆的创建2.3 建堆时间复杂度2.4 堆的插入2.5 堆的删除2.6 堆的代码实现2.6.1 结构体2.6.2 初始化2.6.3 销毁2.6.4 插入2.6.5 删除2.6.6 获取堆顶2.6.7 判空2.6.8 个数2.6.9 向上调整2.6.10 向下调整3. 堆的实现测试测试1测试2测试3测试4向上调整建堆测试5向下调整建堆测试6 4. 堆的应用4.1 堆排序4.2 TOP-K问题 5. test.c文件6. Heap.c7. Heap.h 1. 堆的概念和特点
定义 堆通常可以被看作是一棵完全二叉树的数组对象。这意味着堆的物理结构本质上是顺序存储的线性的但在逻辑上则表现为完全二叉树的逻辑存储结构。 堆总是满足堆性质堆中某个结点的值总是不大于最大堆或不小于最小堆其父结点的值。分类 根据堆顶元素的大小堆可以分为最大堆大根堆和最小堆小根堆。最大堆的根结点值是所有元素中的最大值而最小堆的根结点值是所有元素中的最小值。 常见的堆类型还包括二叉堆和斐波那契堆等。结构 堆的物理结构是一维数组数组的容量和元素个数是堆的重要属性。 在堆中一个结点的父节点可以通过该结点的索引值整除2得到
2. 堆的实现
2.1 堆向下调整算法
现在我们给出一个数组逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提左右子树必须是一个堆才能调整。
int array[] {27,15,19,18,28,34,65,49,25,37};2.2堆的创建
下面我们给出一个数组这个数组逻辑上可以看做一颗完全二叉树但是还不是一个堆现在我们通过算法把它构建成一个堆。根节点左右子树不是堆我们怎么调整呢这里我们从倒数的第一个非叶子节点的子树开始调整一直调整到根节点的树就可以调整成堆。
int a[] {1,5,3,8,7,6};2.3 建堆时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的 就是近似值多几个节点不影响最终结果) 因此建堆的时间复杂度为O(N)。
2.4 堆的插入
先插入一个10到数组的尾上再进行向上调整算法直到满足堆。
2.5 堆的删除
删除堆是删除堆顶的数据将堆顶的数据根最后一个数据一换然后删除数组最后一个数据再进行向下调整算法。
2.6 堆的代码实现
2.6.1 结构体
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;2.6.2 初始化
//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-capacity 0;php-size 0;
}2.6.3 销毁
//销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity 0;php-size 0;
}2.6.4 插入
//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(HeapPush);return;}php-a tmp;php-capacity newCapacity;}//插入数据php-a[php-size] x;php-size;//向上调整AdjustUp(php-a, php-size - 1);
}2.6.5 删除
//删除堆顶的数据
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}2.6.6 获取堆顶
//获取堆顶
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}2.6.7 判空
//判空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}2.6.8 个数
//个数
int HeapSize(HP* php)
{assert(php);return php-size;
}2.6.9 向上调整
//向上调整
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent; parent (child - 1) / 2;}else{break;}}
}2.6.10 向下调整
//向下调整
void AdjustDown(int* a, int n, int parent)
{//假设最小int child parent * 2 1;while (child n){//选出左右孩子小的那个if (child1 n a[child 1] a[child]){child;}//不用管哪个最小if (a[child] a[parent]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}3. 堆的实现测试
测试1
//堆的实现测试
void HeapTest1()
{HP hp;HeapInit(hp);int a[] { 65,100,70,32,50,60 };int sz sizeof(a) / sizeof(a[0]);for (int i 0; i sz; i){HeapPush(hp, a[i]);}HeapDestroy(hp);
}测试2
void HeapTest1()
{HP hp;HeapInit(hp);int a[] { 65,100,70,32,50,60 };int sz sizeof(a) / sizeof(a[0]);for (int i 0; i sz; i){HeapPush(hp, a[i]);}HeapPop(hp);HeapDestroy(hp);
}测试3
void HeapTest1()
{HP hp;HeapInit(hp);int a[] { 65,100,70,32,50,60 };int sz sizeof(a) / sizeof(a[0]);for (int i 0; i sz; i){HeapPush(hp, a[i]);}//HeapPop(hp);while (!HeapEmpty(hp)){int top HeapTop(hp);printf(%d\n, top);HeapPop(hp);}HeapDestroy(hp);
}测试4
//top-k问题
//方法1弊端: 先有一个堆太麻烦空间复杂度高还得拷贝数据。
void HeapSort(int* a, int n)
{HP hp;HeapInit(hp);for (int i 0; i n; i){HeapPush(hp, a[i]);}int i 0;while (!HeapEmpty(hp)){int top HeapTop(hp);a[i] top;HeapPop(hp);}HeapDestroy(hp);
}向上调整建堆测试5
void HeapSort2(int* a, int n)
{//升序-- 建小堆//降序-- 建大堆//向上调整建堆for (int i 1; i n; i){AdjustUp(a, i);}//向下调整建堆/*for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}*/int end n - 1;while (end 0){//交换Swap(a[0], a[end]);//再调整选出次小的AdjustDown(a, end, 0);end--;}
}向下调整建堆测试6
//方法2
void HeapSort2(int* a, int n)
{//升序-- 建小堆//降序-- 建大堆//向上调整建堆/*for (int i 1; i n; i){AdjustUp(a, i);}*///向下调整建堆for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}int end n - 1;while (end 0){//交换Swap(a[0], a[end]);//再调整选出次小的AdjustDown(a, end, 0);end--;}
}4. 堆的应用
4.1 堆排序
堆排序即利用堆的思想来进行排序总共分为两个步骤
建堆 升序建大堆 降序建小堆利用堆删除思想来进行排序 建堆和堆删除中都用到了向下调整因此掌握了向下调整就可以完成堆排序。
4.2 TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
用数据集合中前K个元素来建堆 前k个最大的元素则建小堆 前k个最小的元素则建大堆用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
5. test.c文件
#define _CRT_SECURE_NO_WARNINGS 1
#includeHeap.h//堆的实现测试
void HeapTest1()
{HP hp;HeapInit(hp);int a[] { 65,100,70,32,50,60 };int sz sizeof(a) / sizeof(a[0]);for (int i 0; i sz; i){HeapPush(hp, a[i]);}//HeapPop(hp);while (!HeapEmpty(hp)){int top HeapTop(hp);printf(%d\n, top);HeapPop(hp);}HeapDestroy(hp);
}//top-k问题
//方法1弊端: 先有一个堆太麻烦空间复杂度高还得拷贝数据。
void HeapSort(int* a, int n)
{HP hp;HeapInit(hp);for (int i 0; i n; i){HeapPush(hp, a[i]);}int i 0;while (!HeapEmpty(hp)){int top HeapTop(hp);a[i] top;HeapPop(hp);}HeapDestroy(hp);
}//方法2
void HeapSort2(int* a, int n)
{//升序-- 建小堆//降序-- 建大堆//向上调整建堆for (int i 1; i n; i){AdjustUp(a, i);}//向下调整建堆/*for (int i (n - 1 - 1) / 2; i 0; --i){AdjustDown(a, n, i);}*/int end n - 1;while (end 0){//交换Swap(a[0], a[end]);//再调整选出次小的AdjustDown(a, end, 0);end--;}
}int main()
{//HeapTest1();int a[] { 7,8,3,5,1,9,5,4 };HeapSort2(a, sizeof(a) / sizeof(a[0]));return 0;
}6. Heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include Heap.h//初始化
void HeapInit(HP* php)
{assert(php);php-a NULL;php-capacity 0;php-size 0;
}//销毁
void HeapDestroy(HP* php)
{assert(php);free(php-a);php-a NULL;php-capacity 0;php-size 0;
}//交换
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p2;*p2 *p1;*p1 tmp;
}//向上调整
void AdjustUp(HPDataType* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent; parent (child - 1) / 2;}else{break;}}
}//插入
void HeapPush(HP* php, HPDataType x)
{assert(php);//扩容if (php-size php-capacity){int newCapacity php-capacity 0 ? 4 : php-capacity * 2;HPDataType* tmp (HPDataType*)realloc(php-a, newCapacity * sizeof(HPDataType));if (tmp NULL){perror(HeapPush);return;}php-a tmp;php-capacity newCapacity;}//插入数据php-a[php-size] x;php-size;//向上调整AdjustUp(php-a, php-size - 1);
}//向下调整
void AdjustDown(int* a, int n, int parent)
{//假设最小int child parent * 2 1;while (child n){//选出左右孩子小的那个if (child1 n a[child 1] a[child]){child;}//不用管哪个最小if (a[child] a[parent]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}//删除堆顶的数据
void HeapPop(HP* php)
{assert(php);assert(!HeapEmpty(php));Swap(php-a[0], php-a[php-size - 1]);php-size--;AdjustDown(php-a, php-size, 0);
}//获取堆顶
HPDataType HeapTop(HP* php)
{assert(php);assert(!HeapEmpty(php));return php-a[0];
}//判空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}//个数
int HeapSize(HP* php)
{assert(php);return php-size;
}7. Heap.h
#pragma once#include stdlib.h
#include assert.h
#include stdbool.h
#include stdio.htypedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;//初始化
void HeapInit(HP* php);//销毁
void HeapDestroy(HP* php);//插入
void HeapPush(HP* php, HPDataType x);//删除
void HeapPop(HP* php);//获取堆顶
HPDataType HeapTop(HP* php);//判空
bool HeapEmpty(HP* php);//个数
int HeapSize(HP* php);//向上调整
void AdjustUp(HPDataType* a, int child);//向下调整
void AdjustDown(int* a, int n, int parent);
