什麼是雙向堆？

Question

我讀一本關於人工智能，目前瞭解的尋路（目前正在進行的Dijkstra算法）

在示例代碼中他使用的東西，他呼籲爲雙向堆實現的IndexedPriorityQueue。我找不到有關Google上雙向堆的信息。

該搜索算法是使用索引優先級隊列實現的。 優先級隊列（簡稱爲PQ）是一個隊列，它保持其元素 按優先級順序排序（當時沒有意外）。可以利用這種類型的數據結構來按照距源節點距離（成本） 的增加的順序在搜索邊界上存儲邊緣的目標節點。該方法保證PQ前面 處的節點將是不在SPT上的最接近源節點的 的節點。

這是它被如何實現的：

//----------------------- IndexedPriorityQLow --------------------------- 
// 
// Priority queue based on an index into a set of keys. The queue is 
// maintained as a 2-way heap. 
// 
// The priority in this implementation is the lowest valued key 
//------------------------------------------------------------------------ 
template<class KeyType> 
class IndexedPriorityQLow 
{ 
private: 

    std::vector<KeyType>& m_vecKeys; 

    std::vector<int>  m_Heap; 

    std::vector<int>  m_invHeap; 

    int     m_iSize, 
         m_iMaxSize; 

    void Swap(int a, int b) 
    { 
    int temp = m_Heap[a]; m_Heap[a] = m_Heap[b]; m_Heap[b] = temp; 

    //change the handles too 
    m_invHeap[m_Heap[a]] = a; m_invHeap[m_Heap[b]] = b; 
    } 

    void ReorderUpwards(int nd) 
    { 
    //move up the heap swapping the elements until the heap is ordered 
    while ((nd>1) && (m_vecKeys[m_Heap[nd/2]] > m_vecKeys[m_Heap[nd]])) 
    {  
     Swap(nd/2, nd); 

     nd /= 2; 
    } 
    } 

    void ReorderDownwards(int nd, int HeapSize) 
    { 
    //move down the heap from node nd swapping the elements until 
    //the heap is reordered 
    while (2*nd <= HeapSize) 
    { 
     int child = 2 * nd; 

     //set child to smaller of nd's two children 
     if ((child < HeapSize) && (m_vecKeys[m_Heap[child]] > m_vecKeys[m_Heap[child+1]])) 
     { 
     ++child; 
     } 

     //if this nd is larger than its child, swap 
     if (m_vecKeys[m_Heap[nd]] > m_vecKeys[m_Heap[child]]) 
     { 
     Swap(child, nd); 

     //move the current node down the tree 
     nd = child; 
     } 

     else 
     { 
     break; 
     } 
    } 
    } 


public: 

    //you must pass the constructor a reference to the std::vector the PQ 
    //will be indexing into and the maximum size of the queue. 
    IndexedPriorityQLow(std::vector<KeyType>& keys, 
         int    MaxSize):m_vecKeys(keys), 
               m_iMaxSize(MaxSize), 
               m_iSize(0) 
    { 
    m_Heap.assign(MaxSize+1, 0); 
    m_invHeap.assign(MaxSize+1, 0); 
    } 

    bool empty()const{return (m_iSize==0);} 

    //to insert an item into the queue it gets added to the end of the heap 
    //and then the heap is reordered from the bottom up. 
    void insert(const int idx) 
    { 
    assert (m_iSize+1 <= m_iMaxSize); 

    ++m_iSize; 

    m_Heap[m_iSize] = idx; 

    m_invHeap[idx] = m_iSize; 

    ReorderUpwards(m_iSize); 
    } 

    //to get the min item the first element is exchanged with the lowest 
    //in the heap and then the heap is reordered from the top down. 
    int Pop() 
    { 
    Swap(1, m_iSize); 

    ReorderDownwards(1, m_iSize-1); 

    return m_Heap[m_iSize--]; 
    } 

    //if the value of one of the client key's changes then call this with 
    //the key's index to adjust the queue accordingly 
    void ChangePriority(const int idx) 
    { 
    ReorderUpwards(m_invHeap[idx]); 
    } 
}; 

誰能給我一個2路堆是什麼信息？

Answer 1

「雙向堆」只是指標準heap data structure。這段代碼展示了實現它的一種非常常見的方式，即通過將堆的樹形結構展平成一個數組，使節點的父節點的索引始終爲節點索引的一半（向下舍入）。

Answer 2

它被實現爲一個雙向堆，因爲他省略了堆中的0索引以使父子計算更容易，但關鍵值vektor從0索引開始，所以反轉堆存儲索引，以便堆堆女巫存儲索引keyVector從keyVector獲得適當的值的key，你將需要做這樣的keyVector [heap [invHeap [itemIndex]]]其餘的代碼只是標準的二進制堆實現。