«
»

Heap (maxheap) implementation

March 17, 2012, 12:05 am

A simple, rough and ready, maxheap implementation. It uses an vector as an implicit complete binary tree:

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
class Heap {
 
public:
 
  Heap() {
    store.push_back(0);
  }
 
  int l_child(int idx) {
    return idx*2;
  }
 
  int r_child(int idx) {
    return (idx*2)+1;
  }
 
  int get_parent(int idx) {
    return (idx/2);
  }
 
  void insert(int val) {
    store.push_back(val);
 
    int idx = store.size()-1;
 
    if(idx == 1) return;
 
    // bubble up
    for(;store[get_parent(idx)] < store[idx];) {
      int t = store[get_parent(idx)];
      store[get_parent(idx)] = val;
      store[idx] = t;
      idx = get_parent(idx);
      if(get_parent(idx) == 0) break;
    }
  }
 
  void dump() {
    cout << "DUMPSTART" << endl;
    for(size_t n=0;n<store.size();n++) {
      cout << store[n] << endl;
    }
    cout << "DUMPEND" << endl;
  }
 
  int pop() {
    int r = store[1];
 
    store[1] = store[store.size()-1];
    store.pop_back();
 
    bool min=true;
    int idx = 1;
    for(;min==true;) {
 
      min=false;
 
      int lidx = l_child(idx);
      int ridx = r_child(idx);
  
      int lval;
      int rval;
      if(lidx < store.size()) lval = store[lidx]; else lval = INT_MIN;
      if(ridx < store.size()) rval = store[ridx]; else rval = INT_MIN;
 
      if(store[idx] < lval) { min=true; }
      if(store[idx] < rval) { min=true; }
 
      if(!min) break;
 
      int t = store[idx];
      if(lval > rval) {
        store[idx] = store[l_child(idx)];
        store[l_child(idx)] = t;
        idx = l_child(idx);
      } else {
        store[idx] = store[r_child(idx)];
        store[r_child(idx)] = t;
        idx = r_child(idx);
      }
    }
    return r;
  }
 
  vector<int> store;
};
 
int main() {
 
  vector<int> testdata;
 
  for(size_t n=0;n<10;n++) testdata.push_back(rand()%20);
 
  Heap myheap;
  for(size_t n=0;n<testdata.size();n++) myheap.insert(testdata[n]);
 
  cout << "popping heap:" << endl;
  for(size_t n=0;n<testdata.size();n++) cout << myheap.pop() << endl;
 
  cout << "sorted testdata:" << endl;
  sort(testdata.rbegin(),testdata.rend());
  for(size_t n=0;n<testdata.size();n++) cout << testdata[n] << endl;
  
  cout << "second test: " << endl;
  Heap myheap2;
  for(size_t n=0;n<testdata.size();n++) myheap2.insert(testdata[n]);
  for(size_t n=0;n<(testdata.size()/2);n++) cout << myheap2.pop() << endl;
  myheap2.insert(100);
  myheap2.insert(7);
  for(size_t n=0;n<(testdata.size()/2)+2;n++) cout << myheap2.pop() << endl;
 
}
Category: Uncategorized  |  Comment (RSS)  |  Trackback

Leave a Reply