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

相关文章

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

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

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

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

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

MySQL中的索引结构和分类实战案例详解

《MySQL中的索引结构和分类实战案例详解》本文详解MySQL索引结构与分类,涵盖B树、B+树、哈希及全文索引,分析其原理与优劣势,并结合实战案例探讨创建、管理及优化技巧,助力提升查询性能,感兴趣的朋... 目录一、索引概述1.1 索引的定义与作用1.2 索引的基本原理二、索引结构详解2.1 B树索引2.2
阅读更多...
python3如何找到字典的下标index、获取list中指定元素的位置索引

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》：本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat
阅读更多...
从入门到精通MySQL 数据库索引(实战案例)

从入门到精通MySQL 数据库索引(实战案例)

《从入门到精通MySQL数据库索引(实战案例)》索引是数据库的目录,提升查询速度,主要类型包括BTree、Hash、全文、空间索引,需根据场景选择,建议用于高频查询、关联字段、排序等,避免重复率高或... 目录一、索引是什么？能干嘛？核心作用：二、索引的 4 种主要类型（附通俗例子）1. BTree 索引（
阅读更多...
Java中常见队列举例详解(非线程安全)

Java中常见队列举例详解(非线程安全)

《Java中常见队列举例详解(非线程安全)》队列用于模拟队列这种数据结构,队列通常是指先进先出的容器,：本文主要介绍Java中常见队列(非线程安全)的相关资料,文中通过代码介绍的非常详细,需要的朋... 目录一.队列定义 二.常见接口 三.常见实现类3.1 ArrayDeque3.1.1 实现原理3.1.2
阅读更多...
MySQL 添加索引5种方式示例详解(实用sql代码)

MySQL 添加索引5种方式示例详解(实用sql代码)

《MySQL添加索引5种方式示例详解(实用sql代码)》在MySQL数据库中添加索引可以帮助提高查询性能,尤其是在数据量大的表中,下面给大家分享MySQL添加索引5种方式示例详解(实用sql代码),... 在mysql数据库中添加索引可以帮助提高查询性能，尤其是在数据量大的表中。索引可以在创建表时定义，也可
阅读更多...
C++ RabbitMq消息队列组件详解

C++ RabbitMq消息队列组件详解

《C++RabbitMq消息队列组件详解》：本文主要介绍C++RabbitMq消息队列组件的相关知识,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. RabbitMq介绍2. 安装RabbitMQ3. 安装 RabbitMQ 的 C++客户端库4. A
阅读更多...
golang实现延迟队列(delay queue)的两种实现

golang实现延迟队列(delay queue)的两种实现

《golang实现延迟队列(delayqueue)的两种实现》本文主要介绍了golang实现延迟队列(delayqueue)的两种实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录1 延迟队列：邮件提醒、订单自动取消2 实现2.1 simplChina编程e简单版：go自带的time
阅读更多...
MySQL索引失效问题及解决方案

MySQL索引失效问题及解决方案

《MySQL索引失效问题及解决方案》：本文主要介绍MySQL索引失效问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql索引失效一、概要二、常见的导致MpythonySQL索引失效的原因三、如何诊断MySQL索引失效四、如何解决MySQL索引失
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2