这两个程序实际上就是 算法导论6.5-3和6.5-8的C#实现。在Visual C# 2005下测试通过
186 public class MinHeap
187 {
188 #region Private status
189 private Int32[] m_Array;
190 private Int32 m_Size;
191
192 public Int32 Size { get { return m_Size; } }
193 #endregion
194
195 #region heap tree node navigation
196 internal static Int32 PARENT(Int32 i) { return (i - 1) / 2; }
197 internal static Int32 LEFT(Int32 i) { return 2 * i + 1; }
198 internal static Int32 RIGHT(Int32 i) { return (2 * i + 2); }
199 #endregion
200
201 #region ctor
202 public MinHeap(Int32 size)
203 {
204 if (size < 512) size = 512;
205 m_Array = new Int32[size];
206 m_Size = 0;
207 }
208
209 public MinHeap(Int32[] inputArray)
210 {
211 if (inputArray == null)
212 throw new ArgumentNullException("inputArray", "The input Array cannot be null!");
213 m_Array = inputArray;
214 m_Size = inputArray.Length;
215
216 BuildMinHeap();
217 }
218 #endregion
219
220 #region Build a min heap
221 private void BuildMinHeap()
222 {
223 for (Int32 i = m_Size / 2 - 1; i >= 0; i--) MinHeapify(i);
224 }
225 #endregion
226
227 #region Maintaining the minimal heap property
228 private void MinHeapify(int root)
229 {
230 if (root < 0 || root >= m_Size)
231 throw new ArgumentOutOfRangeException("root", root, "input root node out of range");
232
233 Int32 heapSize = m_Size;
234 Int32 left, right, least ;
235
236 do
237 {
238 least = root;
239 left = LEFT(root);
240 right = RIGHT(root);
241
242 if (left < heapSize && m_Array[left] < m_Array[root]) least = left;
243 if (right < heapSize && m_Array[right] < m_Array[least]) least = right;
244
245 if (least != root)
246 {
247 Common.Exchange(ref m_Array[least], ref m_Array[root]);
248 root = least;
249 continue;
250 }
251 else
252 break;
253 } while (root < heapSize);
254 }
255 #endregion
256
257 #region min-priority queue operations
258 public Int32 Minium {
259 get {
260 if (m_Size < 1) throw new ApplicationException("Heap is empty now!");
261 return m_Array[0];
262 }
263 }
264
265 public Int32 ExtractMin()
266 {
267 if (m_Size < 1) throw new ApplicationException("Heap is empty now!");
268 else if (m_Size == 1) return m_Array[m_Size--];
269
270 Int32 key = m_Array[0];
271 m_Array[0] = m_Array[(m_Size--) - 1];
272 MinHeapify(0);
273
274 return key;
275 }
276
277 public void DecreaseKey(Int32 Index, Int32 Key)
278 {
279 if (Index < 0 || Index >= m_Size)
280 throw new ArgumentOutOfRangeException("Index", Index, "input root node out of range");
281 if (Key > m_Array[Index])
282 throw new ArgumentException("Input value larger than specified element!", "value");
283
284 Int32 parent = PARENT(Index);
285 while (Index > 0)
286 {
287 if (m_Array[parent] > Key)
288 {
289 Common.Exchange(ref m_Array[parent], ref m_Array[Index]);
290 Index = parent;
291 parent = PARENT(Index);
292 }
293 else
294 break;
295 }
296
297 m_Array[Index] = Key;
298 }
299
300 public void Insert(Int32 Key)
301 {
302 // Relocate the storage
303 if (++m_Size > m_Array.Length)
304 {
305 Int32[] newLocationArray = new Int32[m_Array.Length * 2];
306 m_Array.CopyTo(newLocationArray, 0);
307 m_Array = newLocationArray;
308 }
309
310 m_Array[m_Size - 1] = Int32.MaxValue;
311 DecreaseKey(m_Size - 1, Key);
312 }
313 #endregion
314
315 #region Verify the MinHeap
316 public Boolean MinHeapVerify()
317 {
318 for(Int32 i =0; i < m_Size; i++)
319 {
320 if (LEFT(i) < m_Size && m_Array[LEFT(i)] < m_Array[i]) return false;
321 if (RIGHT(i) < m_Size && m_Array[RIGHT(i)] < m_Array[i]) return false;
322 }
323 return true;
324 }
325 #endregion
326
327 #region List the current heap elements
328 public String Show()
329 {
330 // List the current heap elements
331 return Common.ListTheArray(m_Array, m_Size);
332 }
333 #endregion
334 }
Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap for k-way merging.)
public static Int32[] KWayMergeSort(List<Int32[]> InputArrays, Int32 TotalLength)
{
Int32 k = InputArrays.Count; Int32[] output = new Int32[TotalLength]; Int32 outIdx = 0; Int32[] indice = new Int32[k]; //记录各个数组的当前位置 MinHeap heap = new MinHeap(k); //用于排序以及提取最小值的堆 for (Int32 i = 0; i < k; i++) heap.Insert((InputArrays[i])[indice[i]++]); //插入每个数组的首元素 Boolean elementLeft = true; //记录当前所有数组中是否还有剩余的元素 Int32 leastIdx = 0; do
{
output[outIdx++] = heap.ExtractMin(); //插入当前的剩余堆中和数组中的最小元素 elementLeft = false; // 在以下循环中提取首个还有剩余元素的数组的索引，并且判断是否还有剩余的待插入的元素 for (Int32 i = 0; i < k; i++) { if (indice[i] < InputArrays[i].Length) { leastIdx = i; elementLeft = true; break;
} } if (!elementLeft) break; for (Int32 i = leastIdx + 1; i < k; i++) if (indice[i] + 1 < InputArrays[i].Length && InputArrays[i][indice[i]] < InputArrays[leastIdx][indice[leastIdx]]) leastIdx = i; //取得剩余数组中最小元素所在的数组的索引 heap.Insert(InputArrays[leastIdx][indice[leastIdx]++]); //插入剩余数组中的最小元素 } while (elementLeft); while (heap.Size > 0) output[outIdx++] = heap.ExtractMin(); //依次插入堆中剩余的元素 return output;
}