Download Reference Manual
The Developer's Library for D
About Wiki Forums Source Search Contact

root/trunk/tango/util/container/more/Heap.d

Revision 3959, 7.1 kB (checked in by kris, 6 years ago)

fixes #1306 :: Add a minheap and a maxheap data structure to tango.util.container

With thanks to dhasenan

  • Property svn:eol-style set to native
Line 
1 /**
2   *
3   * Copyright:  Copyright (C) 2008 Chris Wright.  All rights reserved.
4   * License:    BSD style: $(LICENSE)
5   * Version:    Oct 2008: Initial release
6   * Author:     Chris Wright, aka dhasenan
7   *
8   */
9
10 module tango.util.container.more.Heap;
11
12 private import tango.core.Exception;
13
14 /** A heap is a data structure where you can insert items in random order and extract them in sorted order.
15   * Pushing an element into the heap takes O(lg n) and popping the top of the heap takes O(lg n). Heaps are
16   * thus popular for sorting, among other things.
17   *
18   * No opApply is provided, since most people would expect this to return the contents in sorted order,
19   * not do significant heap allocation, not modify the collection, and complete in linear time. This
20   * combination is not possible with a heap. */
21
22 struct Heap (T, bool Min)
23 {
24         alias pop       remove;
25         alias push      opCatAssign;
26
27         // The actual data.
28         private T[]     heap;
29        
30         // The index of the cell into which the next element will go.
31         private uint    next;
32
33
34         /** Inserts the given element into the heap. */
35         void push (T t)
36         {
37                 while (heap.length <= next)
38                 {
39                         heap.length = 2 * heap.length + 32;
40                 }
41                 heap[next] = t;
42                 fixup (next);
43                 next++;
44         }
45
46         /** Inserts all elements in the given array into the heap. */
47         void push (T[] array)
48         {
49                 while (heap.length < next + array.length)
50                 {
51                         heap.length = 2 * heap.length + 32;
52                 }
53                 foreach (t; array) push (t);
54         }
55
56         /** Removes the top of this heap and returns it. */
57         T pop ()
58         {
59                 if (next == 0)
60                 {
61                         throw new NoSuchElementException ("Heap :: no elements to pop");
62                 }
63                 next--;
64                 auto t = heap[0];
65                 heap[0] = heap[next];
66                 fixdown(0);
67                 return t;
68         }
69
70         /** Gets the value at the top of the heap without removing it. */
71         T peek ()
72         {
73                 assert (next > 0);
74                 return heap[0];
75         }
76
77         /** Returns the number of elements in this heap. */
78         uint size ()
79         {
80                 return next;
81         }
82
83         /** Reset this heap. */
84         void clear ()
85         {
86                 next = 0;
87         }
88
89         /** Get the reserved capacity of this heap. */
90         uint capacity ()
91         {
92                 return heap.length;
93         }
94
95         /** Reserve enough space in this heap for value elements. The reserved space is truncated or extended as necessary. If the value is less than the number of elements already in the heap, throw an exception. */
96         uint capacity (uint value)
97         {
98                 if (value < next)
99                 {
100                         throw new IllegalArgumentException ("Heap :: illegal truncation");
101                 }
102                 heap.length = value;
103                 return value;
104         }
105
106         /** Return a shallow copy of this heap. */
107         Heap clone ()
108         {
109                 Heap other;
110                 other.heap = this.heap.dup;
111                 other.next = this.next;
112                 return other;
113         }
114
115         // Get the index of the parent for the element at the given index.
116         private uint parent (uint index)
117         {
118                 return (index - 1) / 2;
119         }
120
121         // Having just inserted, restore the heap invariant (that a node's value is greater than its children)
122         private void fixup (uint index)
123         {
124                 if (index == 0) return;
125                 uint par = parent (index);
126                 if (!comp(heap[par], heap[index]))
127                 {
128                 swap (par, index);
129                 fixup (par);
130                 }
131         }
132
133         // Having just removed and replaced the top of the heap with the last inserted element,
134         // restore the heap invariant.
135         private void fixdown (uint index)
136         {
137                 uint left = 2 * index + 1;
138                 uint down;
139                 if (left >= next)
140                 {
141                         return;
142                 }
143
144                 if (left == next - 1)
145                 {
146                         down = left;
147                 }
148                 else if (comp (heap[left], heap[left + 1]))
149                 {
150                         down = left;
151                 }
152                 else
153                 {
154                         down = left + 1;
155                 }
156
157                 if (!comp(heap[index], heap[left]))
158                 {
159                         swap (index, down);
160                         fixdown (down);
161                 }
162         }
163
164         // Swap two elements in the array.
165         private void swap (uint a, uint b)
166         {
167                 auto t = heap[a];
168                 heap[a] = heap[b];
169                 heap[b] = t;
170         }
171
172         private bool comp (T parent, T child)
173         {
174                 static if (Min == true)
175                            return parent <= child;
176                 else
177                            return parent >= child;
178         }
179 }
180
181
182 /** A minheap implementation. This will have the smallest item as the top of the heap. */
183
184 template MinHeap(T)
185 {
186         alias Heap!(T, true) MinHeap;
187 }
188
189 /** A maxheap implementation. This will have the largest item as the top of the heap. */
190
191 template MaxHeap(T)
192 {
193         alias Heap!(T, false) MaxHeap;
194 }
195
196
197 unittest
198 {
199         MinHeap!(uint) h;
200         assert (h.size is 0);
201         h ~= 1;
202         h ~= 3;
203         h ~= 2;
204         h ~= 4;
205         assert (h.size is 4);
206
207         assert (h.peek is 1);
208         assert (h.peek is 1);
209         assert (h.size is 4);
210         h.pop;
211         assert (h.peek is 2);
212         assert (h.size is 3);
213 }
214
215 unittest
216 {
217         MinHeap!(uint) h;
218         assert (h.size is 0);
219         h ~= 1;
220         h ~= 3;
221         h ~= 2;
222         h ~= 4;
223         assert (h.size is 4);
224
225         assert (h.pop is 1);
226         assert (h.size is 3);
227         assert (h.pop is 2);
228         assert (h.size is 2);
229         assert (h.pop is 3);
230         assert (h.size is 1);
231         assert (h.pop is 4);
232         assert (h.size is 0);
233 }
234
235 unittest
236 {
237         MaxHeap!(uint) h;
238         h ~= 1;
239         h ~= 3;
240         h ~= 2;
241         h ~= 4;
242
243         assert (h.pop is 4);
244         assert (h.pop is 3);
245         assert (h.pop is 2);
246         assert (h.pop is 1);
247 }
248
249 unittest
250 {
251         MaxHeap!(uint) h;
252         h ~= 1;
253         h ~= 3;
254         h ~= 2;
255         h ~= 4;
256         auto other = h.clone;
257
258         assert (other.pop is 4);
259         assert (other.pop is 3);
260         assert (other.pop is 2);
261         assert (other.pop is 1);
262         assert (h.size is 4, "cloned heap shares data with original heap");
263         assert (h.pop is 4, "cloned heap shares data with original heap");
264         assert (h.pop is 3, "cloned heap shares data with original heap");
265         assert (h.pop is 2, "cloned heap shares data with original heap");
266         assert (h.pop is 1, "cloned heap shares data with original heap");
267 }
268
269 void main(){}
Note: See TracBrowser for help on using the browser.