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

相关文章

SpringBoot集成redisson实现延时队列教程

SpringBoot集成redisson实现延时队列教程

《SpringBoot集成redisson实现延时队列教程》文章介绍了使用Redisson实现延迟队列的完整步骤,包括依赖导入、Redis配置、工具类封装、业务枚举定义、执行器实现、Bean创建、消费... 目录1、先给项目导入Redisson依赖2、配置redis3、创建 RedissonConfig 配
阅读更多...
RabbitMQ 延时队列插件安装与使用示例详解(基于 Delayed Message Plugin)

RabbitMQ 延时队列插件安装与使用示例详解(基于 Delayed Message Plugin)

《RabbitMQ延时队列插件安装与使用示例详解(基于DelayedMessagePlugin)》本文详解RabbitMQ通过安装rabbitmq_delayed_message_exchan... 目录 一、什么是 RabbitMQ 延时队列？ 二、安装前准备✅ RabbitMQ 环境要求 三、安装延时队
阅读更多...
spring AMQP代码生成rabbitmq的exchange and queue教程

spring AMQP代码生成rabbitmq的exchange and queue教程

《springAMQP代码生成rabbitmq的exchangeandqueue教程》使用SpringAMQP代码直接创建RabbitMQexchange和queue,并确保绑定关系自动成立,简... 目录spring AMQP代码生成rabbitmq的exchange and 编程queue执行结果总结s
阅读更多...
MySQL 索引简介及常见的索引类型有哪些

MySQL 索引简介及常见的索引类型有哪些

《MySQL索引简介及常见的索引类型有哪些》MySQL索引是加速数据检索的特殊结构,用于存储列值与位置信息,常见的索引类型包括：主键索引、唯一索引、普通索引、复合索引、全文索引和空间索引等,本文介绍... 目录什么是 mysql 的索引？常见的索引类型有哪些？总结性回答详细解释1. MySQL 索引的概念2
阅读更多...
Oracle查询表结构建表语句索引等方式

Oracle查询表结构建表语句索引等方式

《Oracle查询表结构建表语句索引等方式》使用USER_TAB_COLUMNS查询表结构可避免系统隐藏字段（如LISTUSER的CLOB与VARCHAR2同名字段）,这些字段可能为dbms_lob.... 目录oracle查询表结构建表语句索引1.用“USER_TAB_COLUMNS”查询表结构2.用“a
阅读更多...
MySQL 强制使用特定索引的操作

MySQL 强制使用特定索引的操作

《MySQL强制使用特定索引的操作》MySQL可通过FORCEINDEX、USEINDEX等语法强制查询使用特定索引,但优化器可能不采纳,需结合EXPLAIN分析执行计划,避免性能下降,注意版本差异... 目录1. 使用FORCE INDEX语法2. 使用USE INDEX语法3. 使用IGNORE IND
阅读更多...
MySQL逻辑删除与唯一索引冲突解决方案

MySQL逻辑删除与唯一索引冲突解决方案

《MySQL逻辑删除与唯一索引冲突解决方案》本文探讨MySQL逻辑删除与唯一索引冲突问题,提出四种解决方案：复合索引+时间戳、修改唯一字段、历史表、业务层校验,推荐方案1和方案3,适用于不同场景,感兴... 目录问题背景问题复现解决方案解决方案1.复合唯一索引 + 时间戳删除字段解决方案2：删除后修改唯一字
阅读更多...
浅谈mysql的not exists走不走索引

浅谈mysql的not exists走不走索引

《浅谈mysql的notexists走不走索引》在MySQL中,​NOTEXISTS子句是否使用索引取决于子查询中关联字段是否建立了合适的索引,下面就来介绍一下mysql的notexists走不走索... 在mysql中，​NOT EXISTS子句是否使用索引取决于子查询中关联字段是否建立了合适的索引。以下
阅读更多...
MySQL之InnoDB存储引擎中的索引用法及说明

MySQL之InnoDB存储引擎中的索引用法及说明

《MySQL之InnoDB存储引擎中的索引用法及说明》：本文主要介绍MySQL之InnoDB存储引擎中的索引用法及说明,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录1、背景2、准备3、正篇【1】存储用户记录的数据页【2】存储目录项记录的数据页【3】聚簇索引【4】二
阅读更多...
全面解析MySQL索引长度限制问题与解决方案

全面解析MySQL索引长度限制问题与解决方案

《全面解析MySQL索引长度限制问题与解决方案》MySQL对索引长度设限是为了保持高效的数据检索性能,这个限制不是MySQL的缺陷,而是数据库设计中的权衡结果,下面我们就来看看如何解决这一问题吧... 目录引言：为什么会有索引键长度问题？一、问题根源深度解析mysql索引长度限制原理实际场景示例二、五大解决
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2