1Generalized heap implementation
2
3Generalized heap is based on usual heap data structure -
4http://en.wikipedia.org/wiki/Heap_%28data_structure%29 .
5
6It provides two additional paremeters, which allow optimizing heap
7for particular cases:
8
9* Fanout. The number of children per each heap node.
10 * Fanout=1 corresponds to sorted List data structure.
11 See http://en.wikipedia.org/wiki/List_%28computing%29 .
12 * Fanout=2 corresponds to Binary heap.
13 See http://en.wikipedia.org/wiki/Binary_heap .
14 * Fanout>2 corresponds to D-heap. See http://en.wikipedia.org/wiki/D-heap .
15 D-heap can be faster than Binary heap in the following cases:
16 * If item comparison is faster than item assignment.
17 * If sequential access to items is faster than non-sequential access
18 to items.
19 * If the number of 'decrease key' operations is larger than the number
20 of 'pop heap' operations for min-heap. This is usually the case
21 for Dijkstra algorithm
22 ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm ).
23
24* PageChunks. The number of chunks per each heap page. Each chunk contains
25 Fanout items, so each heap page contains (PageChunks * Fanout) items.
26 Items inside heap page are organized into a sub-heap with a root item outside
27 the page. Leaf items in the page can be roots pointing to another pages.
28 * PageChunks=1 corresponds to standard heap.
29 * PageChunks>1 corresponds to B-heap. See http://en.wikipedia.org/wiki/B-heap.
30 Heap pages containing more than one page chunk can be useful if multiple
31 item accesses inside heap page is faster than multiple accesses to items
32 across distinct heap pages. This can be the case for systems with virtual
33 memory, where VM pages can be swapped out to slow media.
34 Heap pages can be mapped to VM pages if PageChunks is calculated using
35 the following formula:
36 * PageChunks = sizeof(VM_page) / (sizeof(item) * Fanout)
37 Perfrect alginment between VM pages and heap pages can be achieved if
38 heap's root item is placed at the end of VM page. In this case the first
39 child of the heap's root (i.e. the item with index 1) sits at the beginning
40 of the next VM page.
41
42See also https://github.com/valyala/gheap/tree/sophisticated-gheap branch,
43which contains sophisticated gheap implementation with more complex heap layout
44and low-level optimizations.
45
46
47===============================================================================
48The implementation provides the following functions:
49* Auxiliary functions:
50 * get_parent_index() - returns parent index for the given child.
51 * get_child_index() - returns the first child index for the given parent.
52 * swap_max_item() - swaps heap's maximum item with the item outside heap
53 and restores max heap invariant.
54 * restore_heap_after_item_increase() - restores max heap invariant after
55 the item's value increase.
56 * restore_heap_after_item_decrease() - restores max heap invariant after
57 the item's value decrease.
58 * remove_from_heap() - removes the given item from the heap.
59
60* STL-like functions:
61 * is_heap_until() - returns an iterator to the first non-heap item
62 in the given range.
63 * is_heap() - checks whether the given range contains valid heap.
64 * make_heap() - creates a heap.
65 * push_heap() - pushes the last element in the range to the heap.
66 * pop_heap() - pops up the maximum element from the heap.
67 * sort_heap() - sorts heap items in ascending order.
68
69* Heap-based algorithms:
70 * heapsort() - performs heapsort.
71 * partial_sort() - performs partial sort.
72 * nway_merge() - performs N-way merge on top of the heap.
73 * nway_mergesort() - performs N-way mergesort on top of the heap.
74
75The implementation is inspired by http://queue.acm.org/detail.cfm?id=1814327 ,
76but it is more generalized. The implementation is optimized for speed.
77There are the following files:
78* gheap_cpp03.hpp - gheap optimized for C++03.
79* gheap_cpp11.hpp - gheap optimized for C++11.
80* gheap.hpp - switch file, which includes either gheap_cpp03.hpp
81 or gheap_cpp11.hpp depending on whether GHEAP_CPP11 macro is defined.
82* gheap.h - gheap optimized for C99.
83* galgorithm.hpp - various algorithms on top of gheap for C++.
84* galgorithm.h - various algorithms on top of gheap for C99.
85* gpriority_queue.hpp - priority queue on top of gheap for C++.
86* gpriority_queue.h - priority queue on top of gheap for C99.
87
88Don't forget passing -DNDEBUG option to the compiler when creating optimized
89builds. This significantly speeds up gheap code by removing debug assertions.
90
91There are the following tests:
92* tests.cpp and tests.c - tests for gheap algorithms' correctness.
93* perftests.cpp and perftests.c - performance tests.
94* ops_count_test.cpp - the test, which counts the number of varius operations
95 performed by gheap algorithms.
96
97===============================================================================
98gheap for C++ usage
99
100#include "gheap.hpp"
101
102...
103
104template <class Heap>
105void heapsort(vector<int> &a)
106{
107 Heap::make_heap(a.begin(), a.end());
108 Heap::sort_heap(a.begin(), a.end());
109}
110
111typedef gheap<2, 1> binary_heap;
112heapsort<binary_heap>(a);
113
114typedef gheap<4, 1> d4_heap;
115heapsort<d4_heap>(a);
116
117typedef gheap<2, 512> paged_binary_heap;
118heapsort<paged_binary_heap>(a);
119
120
121===============================================================================
122gheap for C usage
123
124#include "gheap.h"
125
126static void less(const void *const ctx, const void *const a,
127 const void *const b)
128{
129 (void)ctx;
130 return *(int *)a < *(int *)b;
131}
132
133static void move(void *const dst, const void *const src)
134{
135 *(int *)dst = *(int *)src;
136}
137
138static void heapsort(const struct gheap_ctx *const ctx,
139 int *const a, const size_t n)
140{
141 gheap_make_heap(ctx, a, n);
142 gheap_sort_heap(ctx, a, n);
143}
144
145/* heapsort using binary heap */
146static const struct gheap_ctx binary_heap_ctx = {
147 .fanout = 2,
148 .page_chunks = 1,
149 .item_size = sizeof(int),
150 .less_comparer = &less,
151 .less_comparer_ctx = NULL,
152 .item_mover = &move,
153};
154heapsort(&binary_heap_ctx, a, n);
155
156/* heapsort using D-4 heap */
157static const struct gheap_ctx d4_heap_ctx = {
158 .fanout = 4,
159 .page_chunks = 1,
160 .item_size = sizeof(int),
161 .less_comparer = &less,
162 .less_comparer_ctx = NULL,
163 .item_mover = &move,
164};
165heapsort(&d4_heap_ctx, a, n);
166
167/* heapsort using paged binary heap */
168static const struct gheap_ctx paged_binary_heap_ctx = {
169 .fanout = 2,
170 .page_chunks = 512,
171 .item_size = sizeof(int),
172 .less_comparer = &less,
173 .less_comparer_ctx = NULL,
174 .item_mover = &move,
175};
176heapsort(&paged_binary_heap_ctx, a, n);
177