堆实现的优先队列模板

堆排序法c语言代码堆排序法是一种常用的排序算法，它的特点是时间复杂度为O(nlogn)，适用于大数据量的排序。

下面是使用C语言实现的堆排序算法。

1.原理堆排序法的基本思想是将待排序的序列构成一棵完全二叉树，并满足每个节点的值都大于/小于其子节点的值。

首先需要构建一个最大堆顶，将数组的首位和最后一个元素交换，然后将序列长度减一，再将已排序的序列构建堆顶，交换首位元素，以此类推，直到序列长度为一。

最终得到的排序序列就是按照升序或降序排列的。

2.实现#include <stdio.h>#include <stdlib.h>void head_adjust(int arr[], int start, int end);void heap_sort(int arr[], int len);int main(){int arr[] = {5, 9, 1, 4, 2, 8, 0, 3, 6, 7};int len = sizeof(arr) / sizeof(arr[0]);heap_sort(arr, len);for(int i=0; i<len; i++){printf("%d ", arr[i]);}return 0;}/*建立大根堆*/void head_adjust(int arr[], int start, int end){int dad = start;int son = dad*2 + 1;while(son <= end){if(son + 1 <= end && arr[son] < arr[son+1]) {son++;}if(arr[dad] > arr[son]){return;}else{int temp = arr[dad];arr[dad] = arr[son];arr[son] = temp;dad = son;son = dad*2 + 1;}}}/*堆排序*/void heap_sort(int arr[], int len) {for(int i = len/2-1; i>=0; i--) {head_adjust(arr, i, len-1); }for(int i =len-1; i>0; i--){int temp = arr[i];arr[i] = arr[0];arr[0] = temp;head_adjust(arr, 0, i-1);}}3.算法分析时间复杂度：O(nlogn)空间复杂度：O(1)稳定性：不稳定排序方法（可能会交换值相同的元素的相对位置）堆排序法适合数据量较大的排序任务，但在数据量较小时，实现的效率不如插入排序或快速排序。

优先队列升序写法首先，优先队列是一种特殊的队列，其中每个元素都具有一个与之关联的优先级。

当出队时，优先级高的元素先出队，而优先级低的元素则稍后出队。

在升序优先队列中，优先级较高的元素是值越小的元素。

下面，我们将会用中文来讲述升序优先队列的实现方式。

首先，让我们来看看优先队列升序的实现思路：1. 用数组或链表等数据结构来存储元素。

2. 当元素入队时，按照优先级顺序插入到合适的位置。

3. 当元素出队时，取出优先级最高的元素，并删除它。

现在，让我们来详细看看优先队列升序的具体实现方法。

1. 数组实现在使用数组来实现优先队列时，我们需要在数组中存储元素及其优先级。

当元素入队时，我们需要遍历数组并找到第一个比当前元素优先级高的位置，然后将当前元素插入到该位置。

当元素出队时，我们只需要删除数组的最后一个元素即可。

2. 链表实现在使用链表来实现优先队列时，我们需要在链表中存储元素及其优先级。

当元素入队时，我们需要遍历链表并找到第一个比当前元素优先级高的位置，然后将当前元素插入到该位置。

当元素出队时，我们只需要删除链表的第一个元素即可。

3. 堆实现在使用堆来实现优先队列时，我们需要在堆中存储元素及其优先级。

当元素入队时，我们需要插入到堆的末尾，然后进行上浮操作，将元素插入到合适的位置。

当元素出队时，我们需要删除堆顶元素，然后进行下沉操作，将堆中的其他元素重新排列成堆的形式。

无论使用哪种实现方式，都需要注意以下几点：1. 在插入操作时，要确保元素始终按照优先级顺序排列。

2. 在删除操作时，要确保始终取出优先级最高的元素。

3. 在处理异常情况时，要确保代码的健壮性。

总之，在实现优先队列升序时，我们需要注意以下几点：1. 根据具体应用场景选择合适的实现方式。

2. 在插入和删除操作时，要确保始终遵循优先级规则。

3. 考虑到空间和时间复杂度，合理调整数据结构的大小。

以上是升序优先队列的实现方法，希望能对读者有所帮助。

queue的用法和样例队列（Queue）是计算机科学中常用的数据结构，具有先进先出（FIFO）的特性。

队列常用于需要按照顺序处理的场景，例如任务调度、广度优先搜索、缓冲等。

队列的基本操作：1.入队（Enqueue）：将元素添加到队列的尾部。

2.出队（Dequeue）：从队列的头部移除并返回元素。

3.查看头部元素（Front）：查看队列的头部元素，但不移除。

4.判空（isEmpty）：检查队列是否为空。

5.获取队列大小（Size）：获取队列中元素的个数。

队列的实现方式：1.数组实现：使用数组来存储队列元素，通过两个指针分别记录队列头和尾的位置。

但在动态队列中，可能需要考虑数组大小的调整。

public class ArrayQueue<T>{private static final int DEFAULT_CAPACITY =10;private Object[]array;private int front,rear,size;public ArrayQueue(){array =new Object[DEFAULT_CAPACITY];front =rear =size =0;}public void enqueue(T item){if(size ==array.length){resize();}array[rear++]=item;size++;}public T dequeue(){if(isEmpty()){throw new NoSuchElementException("Queue is empty ");}T item =(T)array[front++];size--;return item;}public T front(){if(isEmpty()){throw new NoSuchElementException("Queue is empty ");}return(T)array[front];}public boolean isEmpty(){return size ==0;}public int size(){return size;}private void resize(){int newSize =array.length*2;array =Arrays.copyOf(array,newSize);}}2.链表实现：使用链表来实现队列，每个节点包含一个元素和指向下一个节点的引用。

优先队列的实现（⼤根堆，⼩根堆） 本博客不讲解具体的原理，仅仅给出⼀种优先队列较为⼀般化的，可重⽤性更⾼的⼀种实现⽅法。

我所希望的是能过带来⼀种与使⽤STL相同的使⽤体验，因为学习了STL源码之后深受STL代码的影响，对每个ADT都希望能过给出⼀种⾼效，可重⽤，更⼀般的实现⽅法，即使我的代码在STL的priority_queue⾯前仅仅只是三流⽔平，但也⾜够吧⼆叉堆这种数据结构演绎好了。

为了更⼀般化，我抛弃C语⾔的函数指针，改⽤STL相同的仿函数来实现更加⽅便的⾃定义优先级⽐较函数，于此同时我也兼容了已有类型的原有优先级⽐较仿函数。

⾸先给出maxPriorityQueue的ADT以及默认的优先级⽐较仿函数，默认为⼤根堆，⼩根堆重载优先级⽐较仿函数即可。

#ifndef MAXPRIORITYQUEUE_H#define MAXPRIORITYQUEUE_H#include <cstring>template<class T>struct Compare {bool operator () (const T& a, const T& b) {return a < b;}};template<>struct Compare<char*> {bool operator () (char* s1, char* s2) {return strcmp(s1, s2) < 0;}};template<class T>class maxPriorityQueue {public:~maxPriorityQueue() {}virtual bool empty() const = 0;virtual int size() const = 0;virtual T& top() = 0;virtual void pop() = 0;virtual void push(const T& theElement) = 0;};#endif 对于ADT的设计与实现，在C++中，相应ADT的纯虚类是必不可少的，它是ADT的逻辑定义，是设计数据结构的基础，上述代码给出了maxPriorityQueue的定义以及默认优先级⽐较仿函数，对于仿函数的使⽤⽅法，可在下⾯的maxHeap类中找到。

最⼩堆实现优先队列：Python实现堆是⼀种数据结构，因为Heapsort⽽被提出。

除了堆排序，“堆”这种数据结构还可以⽤于优先队列的实现。

堆⾸先是⼀个完全⼆叉树：它除了最底层之外，树的每⼀层的都是满的，且最底层中的节点处于左边，相互之间没有“跳变”；其次，堆有次序属性：每个节点中的数据项都⼤于或者等于其⼦⼥的数据项（如果是记录，则这些记录中的某个关键域必须满⾜这⼀属性）。

当然，这是指⼤顶堆，⼩顶堆则是⽗节点⽐⼦节点都要⼩。

所谓队列，就是⼀个FIFO表（first in， first out）。

优先队列，就是在队列的基础上，每个元素加⼀个优先级，last in的元素可能会first out，这就是优先级在起作⽤。

我想实现这样⼀个优先队列： 元素为整数 元素值⼩的优先级反⽽⼤ 有⼊队操作，每次进⼊⼀个元素 出队操作，也⾏每次⼀个元素那么，我的⼩根堆Heap应该这样考虑： 每当插⼊元素时，在原有Heap的最后⼀个叶⼦节点后⾯插⼊新元素val，并持续⽐较val和其⽗节点的值之间是否满⾜堆的次序属性，直到满⾜ 每当删除元素时，删除的是值最⼩的元素，也就是根结点root，则将root和最后⼀个叶⼦节点lastleaf互换，然后删除交换后的new_lastleaf ，并从new_root开始调整堆，使满⾜堆的次序属性。

这样⼀来，代码就不难写出：#coding:utf8#author:HaxtraZ#description:优先队列，⽤堆实现#修改⾃《算法导论》2nd Editionclass ZHeap:def __init__(self, item=[]):# 初始化。

item为数组self.items = itemself.heapsize = len(self.items)def LEFT(self, i):return 2 * i + 1def RIGHT(self, i):return 2 * i + 2def PARENT(self, i):return (i - 1) / 2def MIN_HEAPIFY(self, i):# 最⼩堆化：使以i为根的⼦树成为最⼩堆l = self.LEFT(i)r = self.RIGHT(i)if l < self.heapsize and self.items[l] < self.items[i]:smallest = lelse:smallest = iif r < self.heapsize and self.items[r] < self.items[smallest]:smallest = rif smallest != i:self.items[i], self.items[smallest] = self.items[smallest], self.items[i]self.MIN_HEAPIFY(smallest)def INSERT(self, val):# 插⼊⼀个值val，并且调整使满⾜堆结构self.items.append(val)idx = len(self.items) - 1parIdx = self.PARENT(idx)while parIdx >= 0:if self.items[parIdx] > self.items[idx]:self.items[parIdx], self.items[idx] = self.items[idx], self.items[parIdx]idx = parIdxparIdx = self.PARENT(parIdx)else:breakself.heapsize += 1def DELETE(self):last = len(self.items) - 1if last < 0:# 堆为空return None# else:self.items[0], self.items[last] = self.items[last], self.items[0]val = self.items.pop()self.heapsize -= 1self.MIN_HEAPIFY(0)return valdef BUILD_MIN_HEAP(self):# 建⽴最⼩堆, O(nlog(n))i = self.PARENT(len(self.items) - 1)while i >= 0:self.MIN_HEAPIFY(i)i -= 1def SHOW(self):print self.itemsclass ZPriorityQ(ZHeap):def __init__(self, item=[]):ZHeap.__init__(self, item)def enQ(self, val):ZHeap.INSERT(self, val)def deQ(self):val = ZHeap.DELETE(self)return vala = [1, 3, 2, 4, 8, 6, 22, 9]pq = ZPriorityQ()n = len(a)for i in range(n):pq.enQ(a[i])pq.SHOW()for i in range(n):pq.deQ()pq.SHOW() 其中，ZHeap表⽰⼩根堆，ZPriorityQ表⽰优先队列，deQ表⽰退队，enQ表⽰⼊队。

优先队列及其应用场景优先队列是一种常见的数据结构，它在很多应用场景中都有广泛的应用。

本文将介绍优先队列的基本概念、实现方式以及一些常见的应用场景。

一、优先队列的基本概念优先队列是一种特殊的队列，其中每个元素都有一个与之关联的优先级。

在优先队列中，元素的出队顺序不仅取决于它们进入队列的顺序，还取决于它们的优先级。

具有较高优先级的元素会被先出队列，而具有较低优先级的元素会被后出队列。

二、优先队列的实现方式实现优先队列的方法有多种，常见的有两种：基于堆和基于有序数组。

1. 基于堆的优先队列：堆是一种满足堆性质的完全二叉树，可以用数组实现。

在基于堆的优先队列中，堆顶元素具有最高的优先级，每次出队列时都会选择堆中优先级最高的元素。

插入和删除操作的时间复杂度都是O(log n)。

2. 基于有序数组的优先队列：在基于有序数组的优先队列中，元素按照优先级有序排列。

插入操作时，需要找到合适的位置将元素插入到有序数组中；删除操作时，从有序数组中删除优先级最高的元素。

插入的时间复杂度为O(n)，删除的时间复杂度为O(1)。

三、优先队列的应用场景优先队列在很多实际问题中都有重要的应用，下面介绍几个常见的应用场景。

1. 任务调度：在操作系统中，有很多任务需要按照优先级进行调度。

优先队列可以用来存储这些任务，每次选择优先级最高的任务进行调度。

通过合理设置任务的优先级，可以实现高效的任务调度。

2. 模拟系统：在模拟系统中，需要对事件按照发生的顺序进行处理。

优先队列可以用来存储待处理的事件，每次选择发生时间最早的事件进行处理。

通过使用优先队列，可以模拟实际系统中的事件处理过程。

3. 图算法：在图算法中，优先队列可以用来存储待访问的节点或边。

每次选择优先级最高的节点或边进行访问，可以实现一些基于优先级的图算法，如最短路径算法、最小生成树算法等。

4. 哈夫曼编码：哈夫曼编码是一种常见的无损压缩算法，可以将原始数据编码为较短的二进制串。

priority_queue用法小根堆priority_queue是STL库中的一个模板类，它被用来实现优先队列，也就是一个元素集合，每个元素都有一个关键字，可以比较大小，且具有最高优先级的元素总是最先被访问（出队）。

小根堆：在优先队列中，元素的优先级被定义为元素的大小，小的元素优先级高，因此，如果想要实现小根堆，只需要定义一个存放元素的数据结构，比较大小的时候，使用“大于号”（>）进行比较，即将小的元素放在队首（出队），大的元素放在队尾（入队）。

priority_queue的基本操作：1.入队：push()2.出队并返回队首元素：top()3.出队：pop()4.判断队列是否为空：empty()5.求队列中元素的个数：size()下面是一个小根堆的例子：c++#include<iostream>#include<queue>using namespace std;int main() {priority_queue<int,vector<int>,greater<int> > q;定义小根堆int a[] = {54,78,24,65,12,57,93};for(int i=0;i<7;i++) q.push(a[i]);入队while(!q.empty()) {输出队列中的元素cout<<q.top()<<" ";q.pop();出队}return 0;}运行结果：12 24 54 57 65 78 93这里我们使用了std::greater<int>作为比较的方式，因为priority_queue默认是大根堆，而我们要实现小根堆，则需要借助greater类。

C++priority_queue的⽤法（含⾃定义排序⽅式）priority_queue本质是⼀个堆。

1. 头⽂件是#include<queue>2. 关于priority_queue中元素的⽐较 模板申明带3个参数：priority_queue<Type, Container, Functional>，其中Type 为数据类型，Container为保存数据的容器，Functional 为元素⽐较⽅式。

Container必须是⽤数组实现的容器，⽐如vector,deque等等，但不能⽤ list。

STL⾥⾯默认⽤的是vector。

2.1 ⽐较⽅式默认⽤operator<，所以如果把后⾯2个参数缺省的话，优先队列就是⼤顶堆（降序），队头元素最⼤。

特别注意pair的⽐较函数。

以下代码返回⼀个降序输出：1 #include <iostream>2 #include <queue>3 using namespace std;4 int main(){5 priority_queue<int> q;6 for( int i= 0; i< 10; ++i ) q.push(i);7 while( !q.empty() ){8 cout<<q.top()<<endl;9 q.pop();10 }11 return 0;12 }以下代代码返回pair的⽐较结果，先按照pair的first元素降序，first元素相等时，再按照second元素降序：1 #include<iostream>2 #include<vector>3 #include<queue>4 using namespace std;5 int main(){6 priority_queue<pair<int,int> > coll;7 pair<int,int> a(3,4);8 pair<int,int> b(3,5);9 pair<int,int> c(4,3);10 coll.push(c);11 coll.push(b);12 coll.push(a);13 while(!coll.empty())14 {15 cout<<coll.top().first<<"\t"<<coll.top().second<<endl;16 coll.pop();17 }18 return 0;19 }2.2 如果要⽤到⼩顶堆，则⼀般要把模板的3个参数都带进去。