PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
src/MinHeap.cpp
Go to the documentation of this file.
1 /*PGR-MIT*****************************************************************
2 
3 * $Id$
4 *
5 * Project: pgRouting bdsp and bdastar algorithms
6 * Purpose:
7 * Author: Razequl Islam <ziboncsedu@gmail.com>
8 *
9 
10 ------
11 MIT/X license
12 
13 Permission is hereby granted, free of charge, to any person obtaining a copy
14 of this software and associated documentation files (the "Software"), to deal
15 in the Software without restriction, including without limitation the rights
16 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 copies of the Software, and to permit persons to whom the Software is
18 furnished to do so, subject to the following conditions:
19 
20 
21 The above copyright notice and this permission notice shall be included in
22 all copies or substantial portions of the Software.
23 
24 
25 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
26 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
27 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
28 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
29 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
30 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
31 THE SOFTWARE.
32 
33 ********************************************************************PGR-MIT*/
34 
35 #include "./MinHeap.h"
36 #include <string.h>
37 #include <utility>
38 
39 
41  init(maxNode);
42 }
43 
45  reset();
46 }
47 
48 bool MinHeap::reset(void) {
49  if (m_HeapTree != NULL) {
50  delete [] m_HeapTree;
51  m_HeapTree = NULL;
52  }
53  if (m_Index != NULL) {
54  delete [] m_Index;
55  m_Index = NULL;
56  }
57  return true;
58 }
59 
61  m_HeapTree = new PDI[maxNode + 1];
62  m_Index = new int[maxNode + 1];
63  memset(m_Index, -1, sizeof(int) * (maxNode + 1));
65  m_CurrentSize = 0;
66  return true;
67 }
68 
69 void MinHeap::push(PDI node) {
70  int nid = node.second;
71  double ncost = node.first;
72  if (m_Index[nid] != -1) {
73  int pos = m_Index[nid];
74  if (ncost < m_HeapTree[pos].first) {
75  m_HeapTree[pos].first = ncost;
76  shift_up(pos);
77  } else {
78  return;
79  }
80  } else {
81  m_CurrentSize++;
82  m_HeapTree[m_CurrentSize] = node;
83  m_Index[nid] = m_CurrentSize;
85  }
86 }
87 
89  return(m_HeapTree[1]);
90 }
91 
92 bool MinHeap::empty(void) {
93  if (m_CurrentSize == 0)
94  return true;
95  return false;
96 }
97 
98 void MinHeap::pop(void) {
99  if (m_CurrentSize == 0)
100  return;
101  int nid = m_HeapTree[1].second;
102  m_Index[nid] = -1;
104  m_Index[m_HeapTree[1].second] = 1;
105  m_CurrentSize--;
106  shift_down(1);
107 }
108 
109 void MinHeap::shift_up(int node) {
110  while (node > 1) {
111  int par_node = node / 2;
112  if (m_HeapTree[par_node].first <= m_HeapTree[node].first) {
113  return;
114  }
115  PDI temp = m_HeapTree[par_node];
116  m_HeapTree[par_node] = m_HeapTree[node];
117  m_HeapTree[node] = temp;
118  m_Index[m_HeapTree[node].second] = node;
119  m_Index[m_HeapTree[par_node].second] = par_node;
120  node = par_node;
121  }
122  return;
123 }
124 
125 void MinHeap::shift_down(int node) {
126  while (node < m_CurrentSize) {
127  int left_child = node * 2;
128  int right_child = node * 2 + 1;
129  if (left_child > m_CurrentSize) {
130  return;
131  }
132  int smallest = node;
133  if (m_HeapTree[left_child] < m_HeapTree[smallest]) {
134  smallest = left_child;
135  }
136  if (right_child <= m_CurrentSize) {
137  if (m_HeapTree[right_child] < m_HeapTree[smallest]) {
138  smallest = right_child;
139  }
140  }
141  if (node == smallest)
142  return;
143  PDI temp = m_HeapTree[node];
144  m_HeapTree[node] = m_HeapTree[smallest];
145  m_HeapTree[smallest] = temp;
146  m_Index[m_HeapTree[node].second] = node;
147  m_Index[m_HeapTree[smallest].second] = smallest;
148  node = smallest;
149  }
150  return;
151 }
PDI top()
Definition: src/MinHeap.cpp:88
MinHeap(int maxNode)
Definition: src/MinHeap.cpp:40
PDI * m_HeapTree
Definition: src/MinHeap.h:60
void pop()
Definition: src/MinHeap.cpp:98
void shift_up(int node)
std::pair< double, int > PDI
int m_CurrentSize
Definition: src/MinHeap.h:63
bool reset(void)
Definition: src/MinHeap.cpp:48
bool init(int maxNode)
Definition: src/MinHeap.cpp:60
int * m_Index
Definition: src/MinHeap.h:61
int maxNode
Definition: BDATester.cpp:47
bool empty()
Definition: src/MinHeap.cpp:92
void push(PDI node)
Definition: src/MinHeap.cpp:69
~MinHeap(void)
Definition: src/MinHeap.cpp:44
int m_MaxNodeID
Definition: src/MinHeap.h:62
void shift_down(int node)