谷歌网站建设,wordpress添加新页面,apache建wordpress,wordpress 编辑器 空白在数据结构中#xff0c;堆其实就是一棵完全二叉树。我们知道内存中也有一块叫做堆的存储区域#xff0c;但是这与数据结构中的堆是完全不同的概念。在数据结构中#xff0c;堆分为大根堆和小根堆#xff0c;大根堆就是根结点的关键字大于等于任一个子节点的关键字#xf… 在数据结构中堆其实就是一棵完全二叉树。我们知道内存中也有一块叫做堆的存储区域但是这与数据结构中的堆是完全不同的概念。在数据结构中堆分为大根堆和小根堆大根堆就是根结点的关键字大于等于任一个子节点的关键字而它的左右子树又分别都是大根堆小根堆与大根堆恰好相反。在C的STL中优先队列priority_queue结构就是实现的堆结构。下来自己动手现实一个堆结构包括heap_init,heap_insert,heap_top等操作。 1、堆的实现 因为堆是一棵完全二叉树所以我们可以用顺序表来实现而且堆也只能用顺序表。我们用vector。 (1) 堆的初始化 对堆的初始化基本思想首先初始数组是一个杂乱无章的序列但是如果堆中只有一个元素heap[0]那么heap[0]本身是一个堆然后加入heap[1]调整堆继续加入heap[2].....直到完成所有元素的调整。 void sift_up(vectorint heap,int index){while((index1)/2-1 0){if(heap[(index1)/2-1] heap[index]){swap(heap[(index1)/2-1],heap[index]);index (index1)/2-1;}elsebreak;}
}void heap_init(vectorint heap){if(heap.empty())return ;for(int i1; iheap.size(); i){sift_up(heap,i);}
} (2) 向堆中插入元素 把插入的元素放入堆的末尾然后向上调整堆。 void heap_insert(vectorint heap,int element){heap.push_back(element);sift_up(heap,heap.size()-1);
} (3) 取出堆顶的元素 取出一个元素后用最后一个元素填补第一个元素的位置然后向下依次调整堆。 void sift_down(vectorint heap,int index){while(index*22 heap.size()){if(heap[index*21]heap[index*22] heap[index]heap[index*21]){swap(heap[index],heap[index*21]);index index*21;}else if(heap[index*21]heap[index*22] heap[index]heap[index*22]){swap(heap[index],heap[index*22]);index index*22;}elsebreak;}
}
bool heap_top(vectorint heap,int *res){if(heap.empty())return false;*res heap[0];heap[0] heap[heap.size()-1];heap.erase(heap.end()-1);sift_down(heap,0);return true;
} 2、堆排序 首先初始化堆然后依次取出堆顶的值。这里为大根堆所以是从大到小排序。 void heap_sort(vectorint vec){heap_init(vec);int len vec.size();while(len--){int num;heap_top(vec,num);printf(%d ,num);}
} 堆排序的时间复杂度为O(nlog2n)从上面排序的步骤可以看出它是不稳定的排序。但是它与选择排序归并排序一样时间复杂度不随序列的分布变化而变化。而对于插入排序和冒泡排序来说当输入序列有序或者基本有序时它们的复杂度会递减为O(n)而快速排序则会退化成O(n2)。 所以在具体应用中要根据输入序列来选择哪种排序方法具体问题具体分析。由于堆排序特殊的排序结构和优良的性能所以在很多时候下都可以采用堆排序。 3、堆排序的应用 在一个n个数的序列中取其中最大的k个数Top k问题。 这是一个很常见的排序算法题。 方法一直接对这这n个数进行排序然后取k个数。时间复杂度最少为O(nlog2n)。 方法二借鉴快排的思路并不需要完整地实现快排只需要实现快排的一部分即可得到最大的k个数。复杂度为O(nlog2k)。 方法三可以采用哈希排序先把n中开始的k个数放入hash表中然后依次从剩下的的n-k个数中取出一个与hash表中的k个数比较每次淘汰最小的那个数。时间复杂度为O((n-k)*k)。 方法四取出n中开始的k个数建立一个小根堆然后从剩下的n-k个数中每次取出一个数插入小根堆中然后删除堆顶的那个元素堆中的最小值。时间复杂度为O(*(n-k)*lg2k)。 不可否认采用堆来求最大的k个数性能是最好的但是好处还不止这么一点点我们试想一下如果输入的序列很大也就是n值很大以致于无法全部存放在内存中那么这时候方法一和方法二就不管用了当然方法一采用归并排序可以达到目的但是这时候需要多少次IO。如果选择方法四最多只需要(n-k)次IO当然方法三也是如此只是每次需要比较k次。 完整代码详见https://github.com/whc2uestc/DataStructure-Algorithm/tree/master/heap 版权所有欢迎转载转载请注明出处。 转载于:https://www.cnblogs.com/whc-uestc/p/4719355.html
