{"id":4118,"date":"2019-02-03T21:55:26","date_gmt":"2019-02-03T20:55:26","guid":{"rendered":"http:\/\/roboblog.fatal-fury.de\/?p=4118"},"modified":"2019-02-03T21:59:54","modified_gmt":"2019-02-03T20:59:54","slug":"c-guns-acpl-proudly-presents-binaryheap","status":"publish","type":"post","link":"http:\/\/roboblog.fatal-fury.de\/?p=4118","title":{"rendered":"C++ Guns: ACPL proudly presents: BinaryHeap"},"content":{"rendered":"<p>See also<br \/>\n<a href=\"http:\/\/roboblog.fatal-fury.de\/?p=4111\">ACPL: Histogram1D<\/a><br \/>\n<a href=\"http:\/\/roboblog.fatal-fury.de\/?p=4111\">ACPL: Histogram2D<\/a><\/p>\n<p>BinaryHeap as array implemente priority queue. Good for way finding graph algorithmen like dijkstra.<\/p>\n<p>See source code and more code examples at <a href=\"https:\/\/sourceforge.net\/p\/acpl\/code\/ci\/master\/tree\/acpl\/Examples\/BinaryHeap\/README.md\">ACPL Binary Heap<\/a><\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include &lt;core\/util\/StringStream.hpp&gt;\r\n#include &lt;core\/util\/BinaeryHeap.hpp&gt;\r\n\r\nusing namespace acpl;\r\nusing ID = int;\r\n\r\nint main() {\r\n    \/\/ We use a min-heap. The highest priority is the lowest number\r\n    BinaryHeap&lt;double&gt; heap;\r\n    std::map&lt;ID, std::string_view&gt; tasks;\r\n\r\n    \/\/ heap insert returns a ID assiciated with the priority\r\n    tasks.insert({heap.insert(3.0),  &quot;clear drains&quot;});\r\n    tasks.insert({heap.insert(4.0),  &quot;feet cat&quot;});\r\n    tasks.insert({heap.insert(5.0),  &quot;make tea&quot;});\r\n    tasks.insert({heap.insert(1.0),  &quot;solve RC tasks&quot;});\r\n    tasks.insert({heap.insert(2.0),  &quot;tax return&quot;});\r\n    tasks.insert({heap.insert(10.0), &quot;clean room&quot;});\r\n    tasks.insert({heap.insert(99.0), &quot;wash dog&quot;});\r\n\r\n    std::cout &lt;&lt; heap.size() &lt;&lt; &quot; tasks&quot; &lt;&lt; newline;\r\n\r\n    std::cout &lt;&lt; &quot;Most important: &quot;;\r\n    auto firstToDo = heap.extract_minimum();\r\n    std::cout &lt;&lt; tasks&#x5B;firstToDo.second] &lt;&lt; &quot; with priority &quot; &lt;&lt; firstToDo.first &lt;&lt; newline;\r\n    std::cout &lt;&lt; heap.size() &lt;&lt; &quot; tasks left&quot; &lt;&lt; newline;\r\n\r\n    std::cout &lt;&lt; &quot;\\nNext 3 tasks:&quot; &lt;&lt; newline;\r\n    for(int i=0; i &lt; 3; i++) {\r\n        auto task = heap.extract_minimum();\r\n        std::cout &lt;&lt; tasks&#x5B;task.second] &lt;&lt; &quot; with priority &quot; &lt;&lt; task.first &lt;&lt; newline;\r\n    }\r\n\r\n    std::cout &lt;&lt;&quot;make task 'wash the dog' the new first with priority -1&quot; &lt;&lt; newline;\r\n    ID lastInsertedID = tasks.rbegin()-&gt;first;\r\n    heap.decrease_key(lastInsertedID, -1);\r\n\r\n    std::cout &lt;&lt; &quot;\\nThe remaining tasks:&quot; &lt;&lt; newline;\r\n    while(not heap.empty()) {\r\n        auto task = heap.extract_minimum();\r\n        std::cout &lt;&lt; tasks&#x5B;task.second] &lt;&lt; &quot; with priority &quot; &lt;&lt; task.first &lt;&lt; newline;\r\n    }\r\n\r\n    std::cout &lt;&lt; heap.size() &lt;&lt; &quot; tasks left&quot; &lt;&lt; newline;\r\n}\r\n<\/pre>\n<pre>\r\n7 tasks\r\nMost important: solve RC tasks with priority 1\r\n6 tasks left\r\n\r\nNext 3 tasks:\r\ntax return with priority 2\r\nclear drains with priority 3\r\nfeet cat with priority 4\r\nmake task 'wash the dog' the new first with priority -1\r\n\r\nThe remaining tasks:\r\nwash dog with priority -1\r\nmake tea with priority 5\r\nclean room with priority 10\r\n0 tasks left\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>See also ACPL: Histogram1D ACPL: Histogram2D BinaryHeap as array implemente priority queue. Good for way finding graph algorithmen like dijkstra. See source code and more code examples at ACPL Binary Heap #include &lt;core\/util\/StringStream.hpp&gt; #include &lt;core\/util\/BinaeryHeap.hpp&gt; using namespace acpl; using ID = int; int main() { \/\/ We use a min-heap. The highest priority is the [&hellip;]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-4118","post","type-post","status-publish","format-standard","hentry","category-allgemein"],"_links":{"self":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4118","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=4118"}],"version-history":[{"count":3,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4118\/revisions"}],"predecessor-version":[{"id":4125,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=\/wp\/v2\/posts\/4118\/revisions\/4125"}],"wp:attachment":[{"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=4118"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=4118"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/roboblog.fatal-fury.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=4118"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}