优先队列严格说实际上不是一种队列,因为它并不需要遵循队列的FIFO特性,而要求的基本操作包括:向队列中插入新的记录,以及移出队列中的最大的元素。我们可以以各种不同的方式来实现优先队列——只要能够满足上面的两个接口就可以了。但是基于堆的优先队列则具有较好的性能。
优先队列是一种很有用的数据结构,因为实际上我们不是每时每刻都需要对数据进行严格的排序,有时候我们仅仅能够获得最大的元素的即可,但是如果以顺序查找的方式实现的话,效率上根本满足不了要求。而堆则提供了一种较高效率的实现策略。
这里给出一个最小堆的实现,并且结合两个应用进行说明,一个是堆排序,一个是在n个数中寻找第k大的数。
<!--<br />
<br />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br />
http://www.CodeHighlighter.com/<br />
<br />
-->
//Test.cpp:Definestheentrypointfortheconsoleapplication.
//
/**//*
**author:phinecos
**date:7/19/2008
*/
#include"stdafx.h"
#include"PriorityQueue.cpp"
#include<iostream>
usingnamespacestd;
voidprintArray(int*data,intn)
{
inti;
for(i=0;i<n;++i)
{
cout<<data[i]<<"";
}
cout<<endl;
}
voidHeapSort(int*data,intn)
{//堆排序
CPriorityQueue<int>*pQueue=newCPriorityQueue<int>(data,n);
inti;
for(i=0;i<n;++i)
{
data[i]=pQueue->DeleteMin();
}
deletepQueue;
}
intFindKthMax(int*data,intn,intk)
{//在n个数中找第k大的数
CPriorityQueue<int>*pQueue=newCPriorityQueue<int>(data,n);
inti,result;
for(i=0;i<k;++i)
{
result=pQueue->DeleteMin();
}
deletepQueue;
returnresult;
}
intmain(intargc,char*argv[])
{
inta[]={10,32,55,41,39,12,11,15,20,19,21,22,29,25};
intlen=sizeof(a)/sizeof(int);
//堆排序演示
cout<<"排序前:"<<endl;
printArray(a,len);
HeapSort(a,len);
cout<<"排序后:"<<endl;
printArray(a,len);
//寻找第k大数演示
cout<<"请输入k下标:"<<endl;
intk;
cin>>k;
cout<<"第k大数是:"<<FindKthMax(a,len,k)<<endl;
system("pause");
return0;
}
注意:VS2008不支持将模板的声明和实现分开在.h和.cpp中分别实现,总是会报“unresolved external symbol”的错误!这是由于模板具体实例化的特殊因素,导致编译器对分离模式的实现有巨大的复杂度,因而,分离模式至今未能获得大多数编译器的支持。所以在目前的编译环境下,请把模板的声明与定义全部放在.h文件中!否则,视不同的编译器,将会有不可预见的编译及链接错误生成。但我们可以直接include进来cpp文件以骗过编译器
分享到:
相关推荐
@ datastructures-js / priority-queue 使用堆数据结构的性能优先级队列实现。 目录 。尺寸() .toArray() 。清除() 建造 执照 安装 npm install --save @datastructures-js/priority-queue 原料药 此...
Use a binary Max-Heap to implement a Priority Queue. Your priority queue class will be a wrapper for the functions in your heap class. Your heap should be implemented using a list, L. Recall, if a ...
Priority Queue (list based) Bubble sort Selection sort Insertion sort Radix sort Quick sort Merge sort Heap sort Double linked list Skip list Self-organized linked-list ops (move-to-front, move-ahead...
特征快速--- 它通常优于std::priority_queue 。 正如稍后所讨论的,在使用真实工作负载的实验中,它的速度大约快了2 倍。 简单--- 实现在单个头文件中。 测试- 它使用 gcc 4.8 和 clang 3.4 ( ) 进行了单元测试。...
Java实现常用sorting算法,包括insertion, merge, bubble, heap, quick, couting, radix, bucket and maxHeap/Priority queue sorting。并对算法复杂度使用场景做了分析。 主要参考资料wikipedia, CLRS算法教材
本人做的一个二叉堆的课件,附带STL中的priority_queue
Appendix A: Implementing a priority queue as a heap, 104 A.1 A heap, 104 A.1.1 Implementing a heap using an array, 105 a. Maintaining the heap property, 106 A.2 A priority queue using a heap, 109 A.3 ...
源码之前了无秘密,你将看到vector的实现、list的实现、heap的实现、deque的实现、RB-tree的实现、hash-table的实现、set/map 的实现;你将看到各种算法(排序、搜寻、排列组合、数据移动与复制…)的实现;你甚至将...
使用priority_queue(即堆)的不同方式 :mount_fuji: 默认声明 priority_queue< int > pq; // creates max-heap priority_queue< int , vector< int >> pq; // creates max-heap 为 priority_queue 编写...
4.8.2 priority-queue 定义式完整列表 183 4.8.3 priority-queue 没有迭代器 185 4.8.4 priority-queue 测试实例 185 4.9 slist 186 4.9.1 slist 概述 186 4.9.2 slist 的节点 186 4.9.3 slist 的迭代器 188 ...
SwiftUI内功算法代码合集1、Stack ;2、Queue;3、Sorting ;4、Merge Sort;5、Tree Binary;6、Binary Search;7、Heap;8、Priority Queue ; 9、Graph; 10、List ; 11、 Dijkstra ;12 Prim;
Heap.js JavaScript / TypeScript的高效二进制堆(优先级队列,二进制树)数据结构。 包括JavaScript方法,Python的heapq模块方法和Java的PriorityQueue方法。 易于使用,已知接口,经过测试并有据可查JavaScript二...
20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_each 284 21.2 查找容器元素find 285 21.3 条件查找容器元素find_if 286 ...
20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_each 284 21.2 查找容器元素find 285 21.3 条件查找容器元素find_if 286 ...
20.2 priority_queue应用基础 278 20.3 本章小结 281 第四篇 C++ STL算法技术 第21章 非变易算法 284 21.1 逐个容器元素for_each 284 21.2 查找容器元素find 285 21.3 条件查找容器元素find_if 286 ...
测量Heap模板与std :: priority_queue模板的单个实例的编译时间,我得到了80ms与240ms。 对于一次提取最小和一次插入(随机数),I *获得了以下计时: 对于make堆操作 对于场所 最后但并非最不重要的一点是提取(此...
TestPQ.cpp: Priority Queue Demo Sort.h: A collection of sorting and selection routines TestSort.cpp: Test program for sorting and selection routines RadixSort.cpp: Radix sorts DisjSets.h: Header ...
二叉树,指针,非递归实现 Medium 二叉树,指针,in-place,递归深入 Hard 二叉查找树(Binary Search Tree) Easy BST 构造,ref.95 Medium BST,递归解法,动归阙如 Medium BST Hard BST,space O(1) Medium BST ...
Priority queue 66 Map 70 Bidirectional map 73 Multimap 74 Set 75 Tree 80 Arrays 85 Array data structure 85 Row-major order 91 Dope vector 93 Iliffe vector 94 Dynamic array 95 Hashed array tree 98 Gap ...
一个用堆实现的最大优先级队列,支持模板,动态内存申请,一个小例子,VS2008编译通过,大家一起进步。