PGROUTING  2.4
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
tester/MinHeap.h
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 #ifndef MINHEAP_H
36 #define MINHEAP_H
37 
38 #include <string>
39 #include <stdlib.h>
40 #include <iostream>
41 #include <map>
42 #include <math.h>
43 #include <string.h>
44 
45 typedef std::pair<double, int> PDI;
46 
47 class MinHeap
48 {
49 public:
50  MinHeap(int maxNode);
51  ~MinHeap(void);
52 
53  bool reset(void);
54  bool init(int maxNode);
55  void push(PDI node);
56  PDI top();
57  void pop();
58  bool empty();
59 
60 private:
61  void shift_up(int node);
62  void shift_down(int node);
63 
64 private:
65  PDI *m_HeapTree;
66  int *m_Index;
67  int m_MaxNodeID;
68  int m_CurrentSize;
69 
70 };
71 
72 #endif
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
std::pair< double, int > PDI
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)