A simple, rough and ready, maxheap implementation. It uses an vector as an implicit complete binary tree:<\/p>\n
\r\n#include <iostream>\r\n#include <stdlib.h>\r\n#include <vector>\r\n#include <algorithm>\r\n#include <limits.h>\r\n\r\nusing namespace std;\r\n\r\nclass Heap {\r\n\r\npublic:\r\n\r\n Heap() {\r\n store.push_back(0);\r\n }\r\n\r\n int l_child(int idx) {\r\n return idx*2;\r\n }\r\n\r\n int r_child(int idx) {\r\n return (idx*2)+1;\r\n }\r\n\r\n int get_parent(int idx) {\r\n return (idx\/2);\r\n }\r\n\r\n void insert(int val) {\r\n store.push_back(val);\r\n\r\n int idx = store.size()-1;\r\n\r\n if(idx == 1) return;\r\n\r\n \/\/ bubble up\r\n for(;store[get_parent(idx)] < store[idx];) {\r\n int t = store[get_parent(idx)];\r\n store[get_parent(idx)] = val;\r\n store[idx] = t;\r\n idx = get_parent(idx);\r\n if(get_parent(idx) == 0) break;\r\n }\r\n }\r\n\r\n void dump() {\r\n cout << "DUMPSTART" << endl;\r\n for(size_t n=0;n<store.size();n++) {\r\n cout << store[n] << endl;\r\n }\r\n cout << "DUMPEND" << endl;\r\n }\r\n\r\n int pop() {\r\n int r = store[1];\r\n\r\n store[1] = store[store.size()-1];\r\n store.pop_back();\r\n\r\n bool min=true;\r\n int idx = 1;\r\n for(;min==true;) {\r\n\r\n min=false;\r\n\r\n int lidx = l_child(idx);\r\n int ridx = r_child(idx);\r\n \r\n int lval;\r\n int rval;\r\n if(lidx < store.size()) lval = store[lidx]; else lval = INT_MIN;\r\n if(ridx < store.size()) rval = store[ridx]; else rval = INT_MIN;\r\n\r\n if(store[idx] < lval) { min=true; }\r\n if(store[idx] < rval) { min=true; }\r\n\r\n if(!min) break;\r\n\r\n int t = store[idx];\r\n if(lval > rval) {\r\n store[idx] = store[l_child(idx)];\r\n store[l_child(idx)] = t;\r\n idx = l_child(idx);\r\n } else {\r\n store[idx] = store[r_child(idx)];\r\n store[r_child(idx)] = t;\r\n idx = r_child(idx);\r\n }\r\n }\r\n return r;\r\n }\r\n\r\n vector<int> store;\r\n};\r\n\r\nint main() {\r\n\r\n vector<int> testdata;\r\n\r\n for(size_t n=0;n<10;n++) testdata.push_back(rand()%20);\r\n\r\n Heap myheap;\r\n for(size_t n=0;n<testdata.size();n++) myheap.insert(testdata[n]);\r\n\r\n cout << "popping heap:" << endl;\r\n for(size_t n=0;n<testdata.size();n++) cout << myheap.pop() << endl;\r\n\r\n cout << "sorted testdata:" << endl;\r\n sort(testdata.rbegin(),testdata.rend());\r\n for(size_t n=0;n<testdata.size();n++) cout << testdata[n] << endl;\r\n \r\n cout << "second test: " << endl;\r\n Heap myheap2; \r\n for(size_t n=0;n<testdata.size();n++) myheap2.insert(testdata[n]);\r\n for(size_t n=0;n<(testdata.size()\/2);n++) cout << myheap2.pop() << endl;\r\n myheap2.insert(100);\r\n myheap2.insert(7);\r\n for(size_t n=0;n<(testdata.size()\/2)+2;n++) cout << myheap2.pop() << endl;\r\n\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"A simple, rough and ready, maxheap implementation. It uses an vector as an implicit complete binary tree: #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) […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-833","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-dr","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/833","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=833"}],"version-history":[{"count":1,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/833\/revisions"}],"predecessor-version":[{"id":834,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/833\/revisions\/834"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=833"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=833"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=833"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}