-
Notifications
You must be signed in to change notification settings - Fork 0
/
binary_heap.hpp
36 lines (26 loc) · 1000 Bytes
/
binary_heap.hpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <string>
class priority_queue_overflow
{
}; //if insert tries to exceed the size of A then throw priority_queue_overflow()
class priority_queue_underflow
{
}; //if extract_min tries is called on an empty heap then throw priority_queue_overflow()
class priority_queue {
private:
class pair {
public:
std::string object;
double key;
};
pair* A; //the array used to store the heap
int heapsize; //the current heap size
int size; //the current size of the array: does not change
void heapify(int k); //as described in Cormen et al
public:
priority_queue(int n); //don't forget to allocate the array of size n+1 as we don't use slot zero
~priority_queue(); //delete the array
bool empty(); //true/false depending upon whether the heap is empty
void insert(std::string s, double priority); //add s to the heap with the given priority as its key
std::string extract_min(); //remove the string of lowest key and return that string
operator std::string();
};