11 #ifndef ODINAI_PRIORITY_QUEUE_H_
12 #define ODINAI_PRIORITY_QUEUE_H_
15 #include "DebugUtil.h"
31 m_heapHandler(maxSize+1) {}
46 Assert(m_size + 1 <= m_maxSize &&
47 "PriorityQueue::Insert() not enough memory!");
51 m_heap[m_size] = index;
52 m_heapHandler[index] = m_size;
54 ReorderUpwards(m_size);
63 ReorderDownwards(1, m_size - 1);
65 return m_heap[m_size--];
73 ReorderUpwards(m_heapHandler[index]);
76 std::vector<T> &m_keys;
77 std::vector<int> m_heap;
78 std::vector<int> m_heapHandler;
86 void Swap(
int a,
int b)
89 m_heap[a] = m_heap[b];
92 m_heapHandler[m_heap[a]] = a;
93 m_heapHandler[m_heap[b]] = b;
96 void ReorderUpwards(
int n)
100 while(n > 1 && m_keys[m_heap[(halfN = n >> 1)]] > m_keys[m_heap[n]])
108 void ReorderDownwards(
int n,
int heapSize)
112 while((doubleN = n << 1) <= heapSize)
114 if(doubleN < heapSize && m_keys[m_heap[doubleN]] > m_keys[m_heap[doubleN+1]])
119 if(m_keys[m_heap[n]] > m_keys[m_heap[doubleN]])
int Pop()
Definition: PriorityQueue.h:60
void ChangePriority(int index)
Definition: PriorityQueue.h:71
bool Empty() const
Definition: PriorityQueue.h:36
void Insert(int index)
Definition: PriorityQueue.h:44
Definition: PriorityQueue.h:24