做一张简单的app网站多钱,绿色食品网站模板,海外访问国内网站 dns,杭州精品网站建设公司本篇会解决一下几个问题#xff1a; 1.堆是什么#xff1f; 2.如何形成一个堆#xff1f; 3.堆的应用场景 堆是什么#xff1f; 堆总是一颗完全二叉树堆的某个节点总是不大于或不小于父亲节点
如图#xff0c;在小堆中#xff0c;父亲节点总是小于孩子节点的。 如图 1.堆是什么 2.如何形成一个堆 3.堆的应用场景 堆是什么 堆总是一颗完全二叉树堆的某个节点总是不大于或不小于父亲节点
如图在小堆中父亲节点总是小于孩子节点的。 如图在大堆中父亲节点总是大于孩子节点的。 堆和二叉树还是有很大区别的堆是用数组来实现的尽管逻辑结构上是一颗二叉树但在内存上要比二叉树好普通的二叉树你要用链表来存储他们的左右孩子还要给他们分配空间但堆只是用数组来表示。 如何形成一个堆 堆的创建有向上调整和向下调整两种方式。
向上调整从第一个非叶子节点开始向上调整一直调整到根节点。
用int a[] {1,5,3,8,7,6};来做例子
如图所示 向下调整从根节点开始和左右孩子中小或者大的节点比较交换直到小于数组元素。 堆的插入 堆的删除 删除堆是删除堆顶的元素将堆顶的元素根据最后一个数据一换然后删除数组中最后一个元素再进行向下调整算法。
这里想一想为什么要这样
1.因为堆是有数组来创建的如果直接删除堆顶的数据第一个缺点就是会造成移动从后往前覆盖这样就会造成一个问题。兄弟节点变成父子节点而且这样也不能很好的利用数组的优点。
2.如果是交换第一个和最后一个元素这样有2个优点
第一个是不会破坏除了堆顶的左右堆的结构。第二个就是会利用数组的优点数组读取速度很快这样每次最后或最小的元素就放在了后面。 堆的时间复杂度 向下调整时间复杂度 则要移动节点的总步数为 向上调整时间复杂度 则要调整的节点总数为 堆的应用场景 堆排序可以用堆的建立和堆的删除来实现排序堆排序十分稳定相同元素的相对位置不会发生交换而且时间复杂度都是ON*logNTOP-K问题我们想一想王者荣耀中前100的玩家是怎么实现的或者专业前10名...问题
1.先回答一下TOP-K问题即求数据结合中前K个最大的元素或最小的元素一把情况下数据很大。
2.对于这种场景首先想到的就是排序但是数据非常大排序就不可取了因为内存大小的原因不会全部加载到内存这时堆就发生了巨大的优势。
思路利用K个元素建堆如果是求最大的K个元素就建立小堆求最小的K歌元素就建立大堆。然后用N-K个元素与堆顶元素比较满足条件就交换。
下面是源码
void HeapInit(Heap* php)
{assert(php);php-a NULL;php-size php-capacity 0;
}void HeapDestroy(Heap* php)
{assert(php);free(php-a);php-a NULL;php-capacity php-size 0;
}void Swap(HeapDateType* child, HeapDateType* parent){HeapDateType tmp *child;*child *parent;*parent tmp;
}void AdjustUp(HeapDateType* 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(Heap* php,HeapDateType x)
{assert(php);if(php-size php-capacity){int newCapacity php-capacity 0?4:php-capacity*2;HeapDateType* tmp (HeapDateType*)realloc(php-a,sizeof(HeapDateType)*newCapacity);if(tmp NULL){perror(realloc fail\n);}php-a tmp;php-capacity newCapacity;}php-a[php-size] x;php-size;AdjustUp(php-a,php-size-1);
}void HeapPrint(Heap* php)
{assert(php);for(size_t i 0; iphp-size; i){std::cout php-a[i] ;}std::cout std::endl;
}void AdjustDown(HeapDateType* a,int n, int parent)
{int child parent*21;while(child n){if(child1 n a[child1] a[child]){child;}if(a[child] a[parent]){Swap(a[child],a[parent]);parent child;child parent*21;}else{break;}}
}HeapDateType HeapTop(Heap* php)
{assert(php);assert(php-size 0);return php-a[0];
}void HeapPop(Heap* php)
{assert(php);assert(php-size 0);Swap(php-a[0],php-a[php-size-1]);--php-size;AdjustDown(php-a,php-size,0);}bool HeapEmpty(Heap* php)
{assert(php);return php-size 0;
} void HeapSort(int* a, int n)
{//向上调整 O(n*logn)
// for(size_t i 1; in; i){
// AdjustUp(a,i);
// }
////向下调整 O(n)for(int i (n-2)/2; i0; i--){AdjustDown(a,n,i);}//时间复杂度O(N*logN)int end n-1;while(end 0){Swap(a[0],a[end]);AdjustDown(a,end,0);--end;}
}void PrintTopK(const char* filename,int k)
{FILE* fout fopen(filename,r);if(fout NULL){perror(fopen fail);exit(-1);}int* minHeap (int*)malloc(sizeof(int)*k);if(minHeap NULL){perror(malloc fail);exit(-1);}for(int i 0; ik; i){fscanf(fout,%d,minHeap[i]);}for(int i (k-2)/2; i0; i){AdjustDown(minHeap,k,0);}int x 0;while(fscanf(fout,%d,x)! EOF){if(x minHeap[0]){minHeap[0] x;AdjustDown(minHeap,k,0);}}for(int i 0; ik; i){std::cout minHeap[i] ;}std::cout std::endl;
}
