cpp: algorithm: split heap, improve style

cirosantilli · cirosantilli · commit 7f18b9e2205a · 2019-01-11T22:43:43.000Z
diff --git a/cpp/README.md b/cpp/README.md
@@ -82,6 +82,7 @@
             1.  [atomic<bool>](atomic_bool.cpp.off)
         1.  [mutex](mutex.cpp)
     1.  [algorithm](algorithm.cpp)
+        1.  [heap](heap.cpp)
     1.  [functional](functional.cpp)
     1.  [iterator](iterator.cpp)
     1.  [limits](limits.cpp)
diff --git a/cpp/algorithm.cpp b/cpp/algorithm.cpp
@@ -1,7 +1,3 @@
-/*
-# algorithm
-*/
-
 #include "common.hpp"
 
 int main() {
@@ -25,22 +21,21 @@ int main() {
         assert((v == std::vector<int>{1, 0, 2}));
     }
 
-    /*
-    # swap
-
-        Does things equivalent to:
-
-            template <class T> void swap (T& a, T& b)
-            {
-                T c(a); a=b; b=c;
-            }
-
-        However stdlib can specialize it to do operations more efficiently.
-
-        Some stdlib classes implement swap as a method.
-
-        Particularly important because of the copy and swap idiom.
-    */
+    /* # swap
+     *
+     * Does things equivalent to:
+     *
+     *     template <class T> void swap (T& a, T& b)
+     *     {
+     *         T c(a); a=b; b=c;
+     *     }
+     *
+     * However stdlib can specialize it to do operations more efficiently.
+     *
+     * Some stdlib classes implement swap as a method.
+     *
+     * Particularly important because of the copy and swap idiom.
+     */
 
     // # randomize
     {
@@ -56,24 +51,22 @@ int main() {
         assert(v2 == std::vector<int>({3, 2, 0, 1, 3}));
     }
 
-    /*
-    # equal
-
-        Compares ranges of two containers.
-    */
+    /* # equal
+     *
+     * Compares ranges of two containers.
+     */
     {
         std::vector<int> v {0, 1, 2   };
         std::vector<int> v2{   1, 2, 3};
         assert(std::equal(v.begin() + 1, v.end(), v2.begin()));
     }
 
-    /*
-    # accumulate
-
-        Sum over range with operator+
-
-        Also has functional versions http://www.cplusplus.com/reference/numeric/accumulate/
-    */
+    /* # accumulate
+     *
+     * Sum over range with operator+
+     *
+     * Also has functional versions http://www.cplusplus.com/reference/numeric/accumulate/
+     */
     {
         {
             std::vector<int> v{2, 0, 1};
@@ -89,11 +82,10 @@ int main() {
         }
     }
 
-    /*
-    # find
-
-        Return iterator to first found element.
-    */
+    /* # find
+     *
+     * Return iterator to first found element.
+     */
     {
         std::vector<int> v{2,0,1};
         unsigned int pos;
@@ -111,29 +103,27 @@ int main() {
         assert(pos == v.size());
     }
 
-    /*
-    # find_if
-
-        Like find, but using an arbitrary condition on each element instead of equality.
-
-        Consider usage with C++11 lambdas and functional.
-    */
+    /* # find_if
+     *
+     * Like find, but using an arbitrary condition on each element instead of equality.
+     *
+     * Consider usage with C++11 lambdas and functional.
+     */
     {
         std::vector<int> v{2, 0, 1};
         assert(std::find_if (v.begin(), v.end(), odd) == --v.end());
     }
 
-    /*
-    # binary_search
-
-        Container must be already sorted.
-
-        Log complexity.
-
-        Only states if the element is present or not, but does not get its position.
-
-        If you want to get the position of those items, use `equal_range`, `lower_bound` or `upper_bound`.
-    */
+    /* # binary_search
+     *
+     * Container must be already sorted.
+     *
+     * Log complexity.
+     *
+     * Only states if the element is present or not, but does not get its position.
+     *
+     * If you want to get the position of those items, use `equal_range`, `lower_bound` or `upper_bound`.
+     */
     {
 
         std::vector<int> v{0, 1, 2};
@@ -142,37 +132,34 @@ int main() {
         assert(std::binary_search(v.begin(), v.end() - 1, 2) == false);
     }
 
-    /*
-    # lower_bound
-
-        Finds first element in container which is not less than val.
-    */
+    /* # lower_bound
+     *
+     * Finds first element in container which is not less than val.
+     */
     {
         std::vector<int> v{0, 2, 3};
         auto it = std::lower_bound(v.begin(), v.end(), 1);
         assert(it - v.begin() == 1);
     }
 
-    /*
-    # upper_bound
-
-        Finds first element in container is greater than val.
-    */
+    /* # upper_bound
+     *
+     * Finds first element in container is greater than val.
+     */
     {
         std::vector<int> v{0, 1, 2};
         auto it = std::upper_bound(v.begin(), v.end(), 1);
         assert(it - v.begin() == 2);
     }
 
-    /*
-    # equal_range
-
-        Finds first and last location of a value iniside a ranged container.
-
-        Return values are the same as lower_bound and upper_bound.
-
-        log complexity.
-    */
+    /* # equal_range
+     *
+     * Finds first and last location of a value iniside a ranged container.
+     *
+     * Return values are the same as lower_bound and upper_bound.
+     *
+     * log complexity.
+     */
     {
         std::vector<int> v{0, 1, 1, 2};
         std::vector<int>::iterator begin, end;
@@ -197,20 +184,19 @@ int main() {
         assert(*std::min_element(v.begin(), v.end()) == 0);
     }
 
-    /*
-    # advance
-
-        Advance iterator by given number.
-
-        If random access, simply adds + N.
-
-        Else, calls `++` N times.
-
-        Advantage over `+`: only random access containers support `+`,
-        but this works for any container, allowing one to write more general code.
-
-        Beware however that this operation will be slow for non random access containers.
-    */
+    /* # advance
+     *
+     * Advance iterator by given number.
+     *
+     * If random access, simply adds + N.
+     *
+     * Else, calls `++` N times.
+     *
+     * Advantage over `+`: only random access containers support `+`,
+     * but this works for any container, allowing one to write more general code.
+     *
+     * Beware however that this operation will be slow for non random access containers.
+     */
     {
         std::vector<int> v{0, 1, 2};
         auto it = v.begin();
@@ -219,11 +205,10 @@ int main() {
     }
 
 #if __cplusplus >= 201103L
-    /*
-    # next
-
-        Same as advance, but returns a new iterator instead of modifying the old one.
-    */
+    /* # next
+     *
+     * Same as advance, but returns a new iterator instead of modifying the old one.
+     */
     {
         std::vector<int> v{0, 1, 2};
         auto it(v.begin());
@@ -232,125 +217,4 @@ int main() {
         assert(*itNext == 2);
     }
 #endif
-
-    /*
-    # priority queue
-
-        Offers `O(1)` access to the smalles element.
-
-        Other operatoins vary between `O(n)` and `O(1).
-
-        Most common implementaions are via:
-
-        - binary heap
-        - fibonacci heap
-
-        Boost offers explicit heap types: fibonacci, binary and others.
-
-        But no guarantees are made.
-
-        As of C++11, does not support the increase key operation.
-
-        A binary heap without increase key can be implemented via the heap function family under algorithm.
-    */
-
-    /*
-    # heap
-
-        Binary heap implementation.
-
-        <http://en.wikipedia.org/wiki/Heap_%28data_structure%29>
-
-        In short:
-
-        - getting largest element is O(1)
-        - removing the largest element is O(lg) for all implementation
-        - other operations (insertion) may be O(1) or O(lg) depending on the implementation.
-
-        this makes for a good priority queue.
-        Exact heap type is not guaranteed. As of 2013, it seems that most implementations use binary heaps.
-
-        For specific heaps such as Fibonacci, consider [Boost](http://www.boost.org/doc/libs/1_49_0/doc/html/heap.html).
-
-        <http://stackoverflow.com/questions/14118367/stl-for-fibonacci-heap>
-
-        There is no concrete heap data structure in C++:
-        only heap operations over random access data structures.
-        This is why this is under algoritms and is not a data structure of its own.
-
-        There is however a `priority_queue` stdlib container.
-
-        Why random access structure is needed: <https://github.com/cirosantilli/comp-sci/blob/1.0/src/heap.md#array-implementation>
-    */
-    {
-        int myints[]{10, 20, 30, 5, 15};
-        std::vector<int> v(myints, myints + 5);
-
-        /*
-        # make_heap
-
-            Make random access data structure into a heap.
-
-            This changes the element order so that the range has heap properties
-
-            Worst case time: $O(n)$.
-        */
-            std::make_heap(v.begin(), v.end());
-            assert(v.front() == 30);
-
-        /*
-        # pop_heap
-
-            Remove the largest element from the heap.
-
-            That element is moved to the end of the data structure, but since the
-            heap should have its length reduced by one, that element will then be out of the heap.
-
-            Assumes that the input range is already a heap (made with `make_heap` for example).
-        */
-            std::pop_heap(v.begin(), v.end());
-
-            //the element still exists on the data structure
-            assert(v.back() == 30);
-
-            //the second largest element hat become the largets
-            assert(v.front() == 20);
-
-            //remove the element from the data structure definitively
-            v.pop_back();
-
-        /*
-        # push_heap
-
-            Insert element into a heap.
-
-            Assumes that:
-
-            - the range 0 - (end - 1) was already a heap
-            - the new element to be inserted into that heap is at end.
-        */
-
-            //add the new element to the data structure
-            v.push_back(99);
-
-            //reorganize the data so that the last element will be placed in the heap
-            std::push_heap(v.begin(), v.end());
-
-            assert(v.front() == 99);
-
-        /*
-        # sort_heap
-
-            Assumes that the input range is a heap, and sorts it in increasing order.
-
-            The assumption that we have a heap allows for $O(ln)$ sorting,
-            much faster than the optimal bound $O(n log n)$.
-
-            This is exactly what the heapsort alrotithm does: make_heap and then sort_heap.
-        */
-
-            std::sort_heap(v.begin(), v.end());
-            //assert(v)
-            //v == 5 10 15 20 99
-    }
 }
diff --git a/cpp/heap.cpp b/cpp/heap.cpp
