网站建设合同违约条款,北京时事新闻,wordpress分页标签,在合肥做网站前端月薪大概多少目录
1.堆的概念及结构
2.堆的实现
2.1初始化堆
2.2销毁堆
2.3取堆顶元素
2.4返回堆的大小
2.5判断是否为空
2.6打印堆
2.7插入元素
2.8堆的向上调整
2.9弹出元素
2.10堆的向下调整
3. 建堆时间复杂度
4. 堆的应用
4.1 堆排序
4.2 TOP-K问题 1.堆的概念及结构 … 目录
1.堆的概念及结构
2.堆的实现
2.1初始化堆
2.2销毁堆
2.3取堆顶元素
2.4返回堆的大小
2.5判断是否为空
2.6打印堆
2.7插入元素
2.8堆的向上调整
2.9弹出元素
2.10堆的向下调整
3. 建堆时间复杂度
4. 堆的应用
4.1 堆排序
4.2 TOP-K问题 1.堆的概念及结构
堆是一种数据结构它是由一组元素组成的并按照一定的规则进行排序和访问。堆可以看作是一个完全二叉树其中每个节点的值都大于或等于其子节点对于最大堆或小于或等于其子节点对于最小堆。堆通常用来解决具有优先级的问题例如找到最大或最小的元素。 堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值堆总是一棵完全二叉树。 2.堆的实现
这里写的是小根堆大根堆可以在小根堆的基础上稍作修改。下面是堆要实现的一些接口函数
//初始化堆
void HeapInit(HP* php);
//销毁堆
void HeapDestory(HP* php);
//插入元素
void HeapPush(HP* php, HPDataType x);
//堆向上调整算法
void AdjustUp(HP* php, int x);
//弹出堆顶元素
void HeapPop(HP* php);
//堆向下调整算法
void AdjustDwon(HPDataType* a, int size, int x);
//取堆顶元素
HPDataType HeapTop(HP* php);
//返回堆的大小
int HeapSize(HP* php);
//判断是否为空
bool HeapEmpty(HP* php);
//打印堆
void HeapPrint(HP* php);
堆的定义
typedef int HPDataType;
typedef struct Heap
{HPDataType* a;int size;int capacity;
}HP;
对于一些简单的接口函数我们就不详细介绍了在堆中我们主要要学习的是向上调整算法和向下调整算法。这两个函数分别在插入元素和弹出元素的时候会调用。
2.1初始化堆
void HeapInit(HP* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}
2.2销毁堆
void HeapDestory(HP* php)
{assert(php);free(php-a);php-a NULL;php-size php-capacity 0;
}
2.3取堆顶元素
HPDataType HeapTop(HP* php)
{assert(php);return php-a[0];
}
2.4返回堆的大小
int HeapSize(HP* php)
{assert(php);return php-size;
}
2.5判断是否为空
bool HeapEmpty(HP* php)
{assert(php);return php-size 0;
}
2.6打印堆
void HeapPrint(HP* php)
{assert(php);for (int i 0; i php-size; i){printf(%d , php-a[i]);}printf(\n);
}
2.7插入元素
向堆中插入一个元素我们可以将这个元素插入到堆的尾部因为堆的实际存储结构是一个数组我们可以将元素放到数组末尾但如果仅仅是插入到数组末尾的话会将堆的结构给破环我们还需要调用一个向上调整的函数来调整各个节点间的大小关系。
在插入之前需要判断堆的容量是否足够如果堆的容量已满需要扩容这里每次扩容实在原来的基础上扩2倍。
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, sizeof(HPDataType) * newCapacity);if (tmp NULL){printf(realloc fail\n);exit(-1);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;AdjustUp(php-a, php-size);//向上调整php-size;
}
2.8堆的向上调整
在上面插入元素的过程中我们已经使用了堆的向上调整算法下面我们来看看怎么实现这个向上调整算法吧 先插入一个10到数组的尾上再进行向上调整算法直到满足堆。
图示过程 void AdjustUp(HPDataType* a, int x)
{int child x;int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);}else{break;}child parent;parent (child - 1) / 2;}
}
代码分析
初始化变量child为节点xparent为其父节点的索引也即 (child - 1) / 2。进入一个循环该循环会一直执行直到节点x上浮到合适的位置或者到达堆顶。在循环中判断节点x的值是否小于其父节点的值若成立则交换两者的值。若节点x的值不小于父节点的值则跳出循环因为此时堆的性质已满足。更新child和parent的值将child更新为parentparent更新为其父节点的索引也即 (child - 1) / 2。重复步骤3-5直到节点x的值大于或等于其父节点的值或者到达堆顶。
2.9弹出元素
弹出元素就是将堆顶的元素给删除但我们不能直接进行删除这样会将堆的结构给破坏正确的方法是先将堆顶的元素和最后的元素进行交换这样保证的首元素的左子树和右子树依然是堆的形态然后将size自减最后调用一个堆的向下调整函数。 void HeapPop(HP* php)
{assert(php);Swap(php-a[0], php-a[php-size-1]);php-size--;AdjustDwon(php-a, php-size, 0);
}
2.10堆的向下调整
堆的向下调整每次将父节点和左右孩子的较小值进行交换小根堆不断地更新父节点的孩子节点的值。 void AdjustDwon(HPDataType* a, int size, int x)
{int parent x;int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){Swap(a[child], a[parent]);}else{break;}parent child;child parent * 2 1;}
}
初始化变量parent为节点xchild为其左子节点的索引也即 parent * 2 1。进入一个循环该循环会一直执行直到节点x下沉到合适的位置或者没有子节点。在循环中首先判断节点x是否有右子节点并且右子节点的值小于左子节点的值如果成立则将child更新为右子节点的索引。接着判断节点x的值是否大于其子节点的值若成立则交换两者的值。若节点x的值不大于子节点的值则跳出循环因为此时堆的性质已满足。更新parent和child的值将parent更新为childchild更新为parent的左子节点的索引也即 parent * 2 1。重复步骤3-6直到节点x的值小于或等于其子节点的值或者没有子节点。 3. 建堆时间复杂度
因为堆是完全二叉树而满二叉树也是完全二叉树此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值多几个节点不影响最终结果)
向下调整 因此向下调整建堆的时间复杂度为O(N)。
向上调整 因此向上调整建堆的时间复杂度为N*logN; 4. 堆的应用
4.1 堆排序
利用堆排序数组并打印出来
void testHeapSort()
{HP hp;HeapInit(hp);int a[] { 1,4,7,5,10,2,8,9,3,6 };for (int i 0; i sizeof(a) / sizeof(a[0]); i){HeapPush(hp, a[i]);}while (!HeapEmpty(hp)){printf(%d , HeapTop(hp));HeapPop(hp);}//释放内存HeapDestory(hp);
}
int main()
{testHeapSort();return 0;
}
输出结果 但是使用这种方法是不是有点复杂了呢我们要进行堆排序还得先写一个堆的数据结构当然并不是这样的我们可以将代码进行修改在原数组上进行建堆
思路
对于在原数组上进行建堆我们可以使用两种方式
第一种是向上建堆向上建堆的时间复杂度是 O(N*logN)我们不推荐使用这种方法。
第二种是向下建堆它的时间复杂度是O(N它的效率比向上建堆要高。我们推荐使用向下建堆。
还有一个比较让人难以理解的一点是如果要进行升序我们要建大堆如果要进行降序我们要建小堆。 void swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}
void HeapSort(int* a, int n)
{//从倒数第一个非叶子节点开始调for (int i (n - 1 - 1) / 2; i 0; i--){AdjustDwon(a, n, i);//向下调整建堆}int end n - 1;while (end 0){swap(a[0], a[end]);AdjustDwon(a, end, 0);//向下调整[0,end]的元素--end;}
}
int main()
{int a[] { 1,4,7,5,10,2,8,9,3,6 };int n sizeof(a) / sizeof(a[0]);HeapSort(a,n);//堆排序for (int i 0; i n; i){printf(%d , a[i]);}return 0;
} 4.2 TOP-K问题
TOP-K问题即求数据结合中前K个最大的元素或者最小的元素一般情况下数据量都比较大。 比如专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。 对于Top-K问题能想到的最简单直接的方式就是排序但是如果数据量非常大排序就不太可取了(可能 数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决基本思路如下
1. 用数据集合中前K个元素来建堆
前k个最大的元素则建小堆前k个最小的元素则建大堆
2. 用剩余的N-K个元素依次与堆顶元素来比较不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后堆中剩余的K个元素就是所求的前K个最小或者最大的元素。 实际应用在10000000个随机数中找出前十个最大的数字 void AdjustDwon(int* a, int size, int x)
{int parent x;int child parent * 2 1;while (child size){if (child 1 size a[child 1] a[child]){child;}if (a[child] a[parent]){int tmp a[child];a[child] a[parent];a[parent] tmp;}else{break;}parent child;child parent * 2 1;}
}void PrintTopK(int* a, int n, int k)
{int* KMaxHeap (int*)malloc(sizeof(int) * k);assert(KMaxHeap);for (int i 0; i k; i){KMaxHeap[i] a[i];}//建小根堆for (int i (k - 1 - 1) / 2; i 0; i--){AdjustDwon(KMaxHeap, k, i);}//依次比较a数组中剩余的元素for (int i k; i n; i){if (a[i] KMaxHeap[0]){KMaxHeap[0] a[i];}AdjustDwon(KMaxHeap, k, 0);}//打印for (int i 0; i k; i){printf(%d , KMaxHeap[i]);}
}
void testTopK()
{srand(time(0));int n 10000000;int* a (int*)malloc(sizeof(int) * n);for (int i 0; i n; i){a[i] rand() % n;//a[i]的范围[1,n]}//手动设定10个最大的数a[2] n 3;a[122] n 5;a[1233] n 1;a[12333] n 2;a[1322] n 8;a[2312] n 6;a[54612] n 7;a[546612] n 9;a[5612] n 10;a[46612] n 4;PrintTopK(a, n, 10);
}
int main()
{testTopK();return 0;
}
