索引优先队列 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。

相关文章

Redis延迟队列的实现示例

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi
阅读更多...
oracle数据库索引失效的问题及解决

oracle数据库索引失效的问题及解决

《oracle数据库索引失效的问题及解决》本文总结了在Oracle数据库中索引失效的一些常见场景,包括使用isnull、isnotnull、!=、、、函数处理、like前置%查询以及范围索引和等值索引... 目录oracle数据库索引失效问题场景环境索引失效情况及验证结论一结论二结论三结论四结论五总结ora
阅读更多...
Python中列表的高级索引技巧分享

Python中列表的高级索引技巧分享

《Python中列表的高级索引技巧分享》列表是Python中最常用的数据结构之一,它允许你存储多个元素,并且可以通过索引来访问这些元素,本文将带你深入了解Python列表的高级索引技巧,希望对... 目录1.基本索引2.切片3.负数索引切片4.步长5.多维列表6.列表解析7.切片赋值8.删除元素9.反转列表
阅读更多...
MySQL的索引失效的原因实例及解决方案

MySQL的索引失效的原因实例及解决方案

《MySQL的索引失效的原因实例及解决方案》这篇文章主要讨论了MySQL索引失效的常见原因及其解决方案,它涵盖了数据类型不匹配、隐式转换、函数或表达式、范围查询、LIKE查询、OR条件、全表扫描、索引... 目录1. 数据类型不匹配2. 隐式转换3. 函数或表达式4. 范围查询之后的列5. like 查询6
阅读更多...
PostgreSQL如何查询表结构和索引信息

PostgreSQL如何查询表结构和索引信息

《PostgreSQL如何查询表结构和索引信息》文章介绍了在PostgreSQL中查询表结构和索引信息的几种方法,包括使用`d`元命令、系统数据字典查询以及使用可视化工具DBeaver... 目录前言使用\d元命令查看表字段信息和索引信息通过系统数据字典查询表结构通过系统数据字典查询索引信息查询所有的表名可
阅读更多...
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模拟实现
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2