-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathdheap.h
More file actions
executable file
·45 lines (37 loc) · 1.54 KB
/
dheap.h
File metadata and controls
executable file
·45 lines (37 loc) · 1.54 KB
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
37
38
39
40
41
42
43
44
45
// Header file for d-heap data structure. Maintains a subset
// of items in {1,...,m}, where item has a key.
typedef unsigned long keytyp;
typedef int item;
class dheap {
int N; // max number of items in heap
int n; // number of items in heap
int d; // base of heap
item *h; // {h[1],...,h[n]} is set of items
int *pos; // pos[i] gives position of i in h
keytyp *kvec; // kvec[i] is key of item i
item minchild(item); // returm smallest child of item
void siftup(item,int); // move item up to restore heap order
void siftdown(item,int); // move item down to restore heap order
public: dheap(int=100,int=2);
~dheap();
item findmin(); // return the item with smallest key
keytyp key(item); // return the key of item
bit member(item); // return true if item in heap
bit empty(); // return true if heap is empty
void insert(item,keytyp); // insert item with specified key
void remove(item); // remove item from heap
item deletemin(); // delete and return smallest item
void changekey(item,keytyp); // change the key of an item
void print(); // print the heap
int size(); //Added by kun
};
// Return item with smallest key.
inline int dheap::findmin() { return n == 0 ? Null : h[1]; }
// Return key of i.
inline keytyp dheap::key(item i) { return kvec[i]; }
// Return true if i in heap, else false.
inline bit dheap::member(item i) { return pos[i] != Null; }
// Return true if heap is empty, else false.
inline bit dheap::empty() { return n == 0; };
//Return # of elements in heap
inline int dheap::size() { return n;};