索引优先队列 Indexed Priority Queue

2024-02-23 21:50
文章标签 索引 队列 优先 queue priority indexed

本文主要是介绍索引优先队列 Indexed Priority Queue，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

索引优先队列 Indexed Priority Queue的C 语言实现

  1. 索引优先队列定义

​ 在谈论索引优先队列时，无法绕开的话题就是优先队列，那么让我们简单回顾一下优先队列的定义。

1.1 优先队列(Priority Queue=PQ)

​ 优先队列的定义一般用Heap实现，过程中不断对Heap进行操作。常见的有最小优先队列和最大优先队列，最小优先队列的实现依靠min-heap的中元素不断进行上移或下沉操作，在顶部永远对应可比较对象的最小元素；而最大优先队列恰恰相反，其实现逻辑与最小优先队列类似。通过优先队列，可以快速对根元素进行访问和删除操作。

1.2 索引优先队列(Indexed Priority Queue= IPQ)

​ 既然有了优先队列这类数据，为什么还需要引入索引优先队列的概念呢？ 假设我们需要删除队列中的非根元素，那么正常的步骤就需要按照二叉树逐个进行遍历，首先找到此元素的位置，此过程需要花费大量的时间，无法在程序过程中直接访问；找到元素位置之后，和最后一个元素进行交换，再重新调整堆中个元素的位置。整个过程需要大量的遍历和数据移动，不方便程序操作。 为了解决这个问题，就提出了索引优先队列概念，索引优先队列和优先队列实际上有本质的区别。

​ 索引优先队列的核心是维护pm[]和im[]数组，而优先队列的核心是不断交换或调整heap中实际元素；索引优先队列无需对实际元素进行操作，实际上IPQ操作对象为数组的索引号(比如vals[]数组)，通过维护pm[]和im[]数组达到索引化，从而让优先队列的访问更加灵活。

​ pm[]数组，pm(position map)数组实际上映射的是vals数组索引在二叉树上节点的序列号，形象记忆为KN(KeyIndex–>NodeIndex)，通过pm映射，我们可以立即找到某个values的keyindex在优先队列中的节点位置。

​ im[]数组，im(inverse map)实际上是把二叉树上节点的序列号映射到vals数组的索引，形象记忆为(NK)(NodeIndex–>KeyIndex)，通过im映射，我们可以立即找到某个二叉树上节点序列号所对应的keyindex.

IPQ slide

大家可以通过William 的上述标记，进一步理解pm数组和im数组的具体含义。

  1. IPQ的实现(参考Java 版本)

网络上有很多IPQ的java实现版本，比较遗憾的是，还未发现C语言的实现方式，本文拟采用C语言的实现IPQ.

2.1 首先通过结构体建立IPQ所包含的基本对象，包含了基本pm[],im[],values[]以及当前IPQ大小（元素数量)

#if !defined DIJKSTRA_IPQ_Htypedef int IPQElemType;
#endif/*** @brief Define IPQ node struct* @param pm, position map,a given the key index of ki, pm will denote node index* @param im, inverse map, a give the index of node, im will denote the key index* @param sz, current size of IPQ_Node(number of elements)*/
typedef struct IPQ_Node
{int         pm[MAX_SIZE];int         im[MAX_SIZE];IPQElemType   values[MAX_SIZE];int         sz;
}IPQ_Node;

2.2 基本函数

  • swim 函数，Swim函数的作用是，按照比较大小，对pm[], im[]操作，重新向上（float)调整顺序。
void swim(IPQ_Node *Q, int i)
{while (parent(i) >= 0 && less_value(Q->values[Q->im[i]], Q->values[Q->im[parent(i)]])){swap(Q,i,parent(i));i=parent(i);}
}
  • sink 函数，Sink函数的作用是，按照比较大小，对pm[], im[]操作，重新向下(调整）调整顺序。
void sink(IPQ_Node *Q, int i)
{int l;int r;int smallest;l=left(i);r=right(i);if(l<Q->sz && less_value(Q->values[Q->im[l]],Q->values[Q->im[i]])){smallest=l;}else{smallest=i;}if(r<Q->sz && less_value(Q->values[Q->im[r]],Q->values[Q->im[smallest]])){smallest =r;}while(smallest != i){swap(Q,i,smallest);i=smallest;l = left(i);r = right(i); if (l < Q->sz && less_value(Q->values[Q->im[l]], Q->values[Q->im[i]])){smallest = l;}else{smallest = i;}if (r < Q->sz && less_value(Q->values[Q->im[r]], Q->values[Q->im[smallest]])){smallest = r;}}
}

  • swap 函数，这个函数不是交换values数组中的元素，而是维护im[]和pm[]数组

    void swap(IPQ_Node *Q, int i, int j)
{int temp;Q->pm[Q->im[i]]=j;Q->pm[Q->im[j]]=i;temp=Q->im[i];Q->im[i]=Q->im[j];Q->im[j]=temp;
}

  • 求heap 中各节点位置的函数

    int left(int i){return 2*i+1;}int right(int i){return 2*i+2;}int parent(int i){return (i-1)/2;}
  • 比较函数，比较函数可以放在具体的应用中进行实现，比如Dijkstra或者main测试函数中实现，由于本文定义为整型，所以实现起来比较简单。
int less_value(IPQElemType v1, IPQElemType v2)
{return v1<v2;
}

2.3 操作函数实现（具体参考代码）

  1. 参考代码

3.1 头函数文件（IndexedPriorityQueue.h)

/*** @file IndexedPriorityQueue.h* @author your name (you@domain.com)* @brief * Reference code link in the learning note.md documentation* @version 0.1* @date 2023-02-09* * @copyright Copyright (c) 2023* */
#ifndef INDEXPRIORITYQUEUE_H
#define INDEXPRIORITYQUEUE_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>
#define  MAX_SIZE 100#if !defined DIJKSTRA_IPQ_H
typedef int IPQElemType;
#endif/*** @brief Define indexed priority queue node* @param pm, position map, given the key index of ki, pm will denote node index* @param im, inverse map, give the index of node, im will denote the key index* @param sz, current size of IPQ_Node(number of elements)*/
typedef struct IPQ_Node
{int         pm[MAX_SIZE];int         im[MAX_SIZE];IPQElemType   values[MAX_SIZE];int         sz;
}IPQ_Node;/*** @brief Initialize indexed priority queue* * @param Q */
void Init_IPQ(IPQ_Node *Q);/*** @brief Check if ki had been included in the ipq* * @param Q  indexed priority queue* @param ki key index number* @return true * @return false */
bool contains(IPQ_Node Q,int ki);/*** @brief Get the key index of node[0]* @param Q  indexed priority queue* @return int -Key index of node[0]*/
int Peek_MinKeyIndex(IPQ_Node Q);/*** @brief Get the node[0] as the min key index* Remove this element** @param Q Pointer to indexed priority queue* @return int int -Key index of node[0]*/
int Poll_MinKeyIndex(IPQ_Node *Q);/*** @brief Look for the values of node[0]* * @param Q indexed priority queue* @return IPQElemType -Object of IPQElemType*/
IPQElemType Peek_MinValue(IPQ_Node Q);/*** @brief Get the ki from the node[0] and look for the value based on ki** @param Q Pointer to indexed priority queue* @return IPQElemType -Min value from the key index,follow this ki and return */
IPQElemType Poll_MinValue(IPQ_Node *Q);/*** @brief Assign value to a certain of Q->values[], then conduct the swim function** @param Q Pointer to indexed priority queue* @param ki Key index with hashtable* @param value Value(weight/distance etc.) to be assigned to Q->values[]*/
void Insert_KeyValue(IPQ_Node *Q, int ki, IPQElemType value);/*** @brief Acquire the value from values[] based on key index(ki)* * @param ki Key index of pair map* @return IPQElemType -Return IPQElemType object*/
IPQElemType Get_ValueOf(IPQ_Node Q, int ki);/*** @brief Delete the value of key index(ki)* * @param Q Poiner to IPQ_Node* @param ki Key index* @return -IPQElemType IPQElemType object*/
IPQElemType Delete_ValueOf(IPQ_Node *Q, int ki);/*** @brief Update the value at ki locatoin, then execute swim() and sink() function* * @param Q Pointer to IPQ_Node* @param ki Key index* @param value new value* @return IPQElemType -Return the old value */
IPQElemType Update_ValueOf(IPQ_Node *Q, int ki,IPQElemType value);/*** @brief Decrease the value at the location of ki to new value(value)* * @param Q Pointer to IPQ_Node* @param ki Key index* @param value -New value(decreased to this value)*/
void Decrease_Valueof(IPQ_Node *Q, int ki, IPQElemType value);/*** @brief Increase the value at the location of ki to new value(value)** @param Q Pointer to IPQ_Node* @param ki Key index* @param value -New value(increased to this value)*/
void Increase_Valueof(IPQ_Node *Q, int ki, IPQElemType value);/*It will list the helper function in next section
*//*** @brief Return the left child of index i* * @param i parent index* @return int */
int left(int i);/*** @brief Return the right child of index i* * @param i current index* @return int return the index of right child*/
int right(int i);/*** @brief Return the parent node of index i** @param i current index* @return int return the index of right child*/
int parent(int i);/*** @brief Float up since node[i]* * @param Q Pointer to IPQ_Node* @param i Index of node(node[i]) */
void swim(IPQ_Node *Q, int i);/*** @brief Sink down since node[i]** @param Q Pointer to IPQ_Node* @param i Index of node(node[i])*/
void sink(IPQ_Node *Q, int i);/*** @brief Update the pm[] and i[] in the IPQ_Node* * @param Q Pointer to IPQ_Node* @param i Index of node i(node[i])* @param j Index of node j(node[j])*/
void swap(IPQ_Node *Q, int i, int j);/*** @brief Compare index of array* * @param i index i* @param j index j* @return int return i<j;*/
int less_index(int i, int j);/*** @brief Compare the value of IPQElemType v1 and v2* IPQElement should be comparable* * @param v1 First value* @param v2 Second value* @return int return v1<v2(comparable)*/
int less_value(IPQElemType v1, IPQElemType v2);#endif

2.2 函数的实现C语言实现文件(IndexedPriorityQueue.c)

/*** @file IndexedPriorityQueue.c* @author your name (you@domain.com)* @brief * @version 0.1* @date 2023-02-09* * @copyright Copyright (c) 2023* */#ifndef INDEXPRIORITYQUEUE_C
#define INDEXPRIORITYQUEUE_C
#include "IndexedPriorityQueue.h"void swim(IPQ_Node *Q, int i)
{while (parent(i) >= 0 && less_value(Q->values[Q->im[i]], Q->values[Q->im[parent(i)]])){swap(Q,i,parent(i));i=parent(i);}
}void sink(IPQ_Node *Q, int i)
{int l;int r;int smallest;l=left(i);r=right(i);if(l<Q->sz && less_value(Q->values[Q->im[l]],Q->values[Q->im[i]])){smallest=l;}else{smallest=i;}if(r<Q->sz && less_value(Q->values[Q->im[r]],Q->values[Q->im[smallest]])){smallest =r;}while(smallest != i){swap(Q,i,smallest);i=smallest;l = left(i);r = right(i); if (l < Q->sz && less_value(Q->values[Q->im[l]], Q->values[Q->im[i]])){smallest = l;}else{smallest = i;}if (r < Q->sz && less_value(Q->values[Q->im[r]], Q->values[Q->im[smallest]])){smallest = r;}}
}void swap(IPQ_Node *Q, int i, int j)
{int temp;Q->pm[Q->im[i]]=j;Q->pm[Q->im[j]]=i;temp=Q->im[i];Q->im[i]=Q->im[j];Q->im[j]=temp;
}int left(int i)
{return 2*i+1;
}int right(int i)
{return 2*i+2;
}int parent(int i)
{return (i-1)/2;
}/* Main function implementation*/void Init_IPQ(IPQ_Node *Q)
{int i;for(i=0;i<MAX_SIZE;i++){Q->pm[i]=-1;Q->im[i]=-1;Q->values[i]=INT_MIN;}Q->sz=0;
}bool contains(IPQ_Node Q, int ki)
{return Q.pm[ki]!=-1;
}int Peek_MinKeyIndex(IPQ_Node Q)
{return Q.im[0];
}int Poll_MinKeyIndex(IPQ_Node *Q)
{int minki;minki= Peek_MinKeyIndex(*Q);Delete_ValueOf(Q,minki);return minki;
}IPQElemType Peek_MinValue(IPQ_Node Q)
{return Q.values[Q.im[0]];
}IPQElemType Poll_MinValue(IPQ_Node *Q)
{IPQElemType minvalue;minvalue = Peek_MinValue(*Q);Delete_ValueOf(Q,Peek_MinKeyIndex(*Q));return minvalue;
}void Insert_KeyValue(IPQ_Node *Q, int ki, IPQElemType value)
{Q->pm[ki]=Q->sz;Q->im[Q->sz]=ki;Q->values[ki]=value;swim(Q,Q->sz);Q->sz++;
}IPQElemType Get_ValueOf(IPQ_Node Q, int ki)
{return Q.values[ki];
}IPQElemType Delete_ValueOf(IPQ_Node *Q, int ki)
{int i;IPQElemType value;i=Q->pm[ki];value=Q->values[ki];Q->sz--;swap(Q,i,Q->sz);sink(Q,i);swim(Q,i);Q->values[ki]=INT_MIN;Q->pm[ki]=-1; //node index set to -1Q->im[Q->sz]=-1;return value;
}IPQElemType Update_ValueOf(IPQ_Node *Q, int ki, IPQElemType value)
{int i;IPQElemType old_value;i=Q->pm[ki];old_value=Q->values[ki];Q->values[ki]=value;sink(Q,i);swim(Q,i);return old_value;
}void Decrease_Valueof(IPQ_Node *Q, int ki, IPQElemType value)
{if (less_value(value, Q->values[ki])){Q->values[ki] = value;swim(Q,Q->pm[ki]);}
}void Increase_Valueof(IPQ_Node *Q, int ki, IPQElemType value)
{if (less_value(Q->values[ki],value)){Q->values[ki] = value;sink(Q,Q->pm[ki]);}
}#endif
  1. 主函数测试(IndexedPriorityQueue_main.c)
/*** @file IndexedPriorityQueue_main.c* @author your name (you@domain.com)* @brief * @version 0.1* @date 2023-02-09* * @copyright Copyright (c) 2023* */#ifndef INDEXPRIORITYQUEUE_MAIN_C
#define INDEXPRIORITYQUEUE_MAIN_C
#include "IndexedPriorityQueue.c"int main(void)
{int ki;int N=5;char *map[]={"jason","mary","jacky","lily","maggy"};int  values[]={3,20,5,9,2};IPQ_Node Q;int minvalue;Init_IPQ(&Q);for(ki=0;ki<N;ki++){Insert_KeyValue(&Q,ki,values[ki]);}Increase_Valueof(&Q,4,7);minvalue=Peek_MinValue(Q);minvalue = Poll_MinValue(&Q);minvalue = Peek_MinValue(Q);printf("\n end \n");getchar();return EXIT_SUCCESS;
}int less_value(IPQElemType v1, IPQElemType v2)
{return v1<v2;
}#endif

  1. 总结

    通过对IPQ的学习和C语言实现，初步掌握了PQ(Priority Queue)和IPQ(Indexed Priority Queue)之间的区别，另外通过C语言实现，将为Dijkstra的eager算法提供了可能。

    IPQ的关键还是理解pm[]和im[]数组，理解这两个数组后，其它的操作都相对比较简单。

    以上，

    谢谢

  2. 总结

    通过对IPQ的学习和C语言实现，初步掌握了PQ(Priority Queue)和IPQ(Indexed Priority Queue)之间的区别，另外通过C语言实现，将为Dijkstra的eager算法提供了可能。

    IPQ的关键还是理解pm[]和im[]数组，理解这两个数组后，其它的操作都相对比较简单。

    以上，

    谢谢

参考文献：

  1. Indexed Priority Queue的Java实现 by William Fiset

https://github.com/williamfiset/Algorithms/blob/master/src/main/java/com/williamfiset/algorithms/datastructures/priorityqueue/MinIndexedDHeap.java#L124

  1. Video Index Priority Queue by William Fiset

https://www.youtube.com/watch?v=jND_WJ8r7FE&t=0s&ab_channel=WilliamFiset

这篇关于索引优先队列 Indexed Priority Queue的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/740036。

相关文章

hdu1180（广搜+优先队列）

hdu1180（广搜+优先队列）

此题要求最少到达目标点T的最短时间，所以我选择了广度优先搜索，并且要用到优先队列。 另外此题注意点较多，比如说可以在某个点停留，我wa了好多两次，就是因为忽略了这一点，然后参考了大神的思想，然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
poj 3190 优先队列+贪心

poj 3190 优先队列+贪心

题意： 有n头牛，分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。 问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s
阅读更多...
poj 2431 poj 3253 优先队列的运用

poj 2431 poj 3253 优先队列的运用

poj 2431： 题意： 一条路起点为0， 终点为l。 卡车初始时在0点，并且有p升油，假设油箱无限大。 给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。 问最少加几次油可以到达终点，若不能到达，输出-1。 解析： 《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一
阅读更多...
C++——stack、queue的实现及deque的介绍

C++——stack、queue的实现及deque的介绍

目录 1.stack与queue的实现 1.1stack的实现  1.2 queue的实现 2.重温vector、list、stack、queue的介绍 2.1 STL标准库中stack和queue的底层结构  3.deque的简单介绍 3.1为什么选择deque作为stack和queue的底层默认容器  3.2 STL中对stack与queue的模拟实现 ①stack模拟实现
阅读更多...
poj3750约瑟夫环，循环队列

poj3750约瑟夫环，循环队列

Description 有N个小孩围成一圈，给他们从1开始依次编号，现指定从第W个开始报数，报到第S个时，该小孩出列，然后从下一个小孩开始报数，仍是报到S个出列，如此重复下去，直到所有的小孩都出列（总人数不足S个时将循环报数），求小孩出列的顺序。 Input 第一行输入小孩的人数N（N<=64） 接下来每行输入一个小孩的名字(人名不超过15个字符) 最后一行输入W,S (W < N)，用
阅读更多...
POJ2010 贪心优先队列

POJ2010 贪心优先队列

c头牛,需要选n头（奇数）；学校总共有f的资金， 每头牛分数score和学费cost，问合法招生方案中,中间分数（即排名第(n+1)/2）最高的是多少。 n头牛按照先score后cost从小到大排序； 枚举中间score的牛,  预处理左边与右边的最小花费和。 预处理直接优先队列贪心 public class Main {public static voi
阅读更多...
Java并发编程之——BlockingQueue（队列）

Java并发编程之——BlockingQueue（队列）

一、什么是BlockingQueue BlockingQueue即阻塞队列，从阻塞这个词可以看出，在某些情况下对阻塞队列的访问可能会造成阻塞。被阻塞的情况主要有如下两种： 1. 当队列满了的时候进行入队列操作2. 当队列空了的时候进行出队列操作123 因此，当一个线程试图对一个已经满了的队列进行入队列操作时，它将会被阻塞，除非有另一个线程做了出队列操作；同样，当一个线程试图对一个空
阅读更多...
ActiveMQ—Queue与Topic区别

ActiveMQ—Queue与Topic区别

Queue与Topic区别 转自：http://blog.csdn.net/qq_21033663/article/details/52458305 队列（Queue）和主题（Topic）是JMS支持的两种消息传递模型：         1、点对点（point-to-point，简称PTP）Queue消息传递模型：         通过该消息传递模型，一个应用程序（即消息生产者）可以
阅读更多...
深度优先（DFS）和广度优先（BFS）——算法

深度优先（DFS）和广度优先（BFS）——算法

深度优先 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2