Enderlook

Binary Min Heap

Sep 19th, 2020
940
327 days
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using Xunit;
  4.  
  5. public class BinaryMinHeapTest
  6. {
  7.     private static readonly int[] sorted = new int[] { -8, -6, 0, 5, 9, 15, 35, 74, 99 };
  8.     private static readonly int[] unsorted = new int[] { 35, -8, 99, 74, -6, 0, 9, 5, 15 };
  9.  
  10.     [Fact]
  11.     public void Test()
  12.     {
  13.         BinaryMinHeap<int> heap = new BinaryMinHeap<int>();
  14.         foreach (int value in unsorted)
  15.             heap.Add(value);
  16.  
  17.         int i = 0;
  18.         while (heap.TryExtract(out int value))
  19.             Assert.Equal(sorted[i++], value);
  20.     }
  21. }
  22.  
  23. public class BinaryMinHeap<T> where T : IComparable<T>
  24. {
  25.     private List<T> items;
  26.  
  27.     public int Count => items.Count;
  28.  
  29.     public int Capacity {
  30.         get => items.Capacity;
  31.         set => items.Capacity = Capacity;
  32.     }
  33.  
  34.     public bool IsEmpty => Count > 0;
  35.  
  36.     public BinaryMinHeap() => items = new List<T>();
  37.  
  38.     public BinaryMinHeap(int capacity)
  39.     {
  40.         if (capacity < 1)
  41.             throw new ArgumentOutOfRangeException(nameof(capacity), "Must be greater than 0");
  42.  
  43.         items = new List<T>(capacity);
  44.     }
  45.  
  46.     public void Clear() => items.Clear();
  47.  
  48.     public void Add(T element)
  49.     {
  50.         items.Add(element);
  51.         MoveUp();
  52.     }
  53.  
  54.     public T Peek()
  55.     {
  56.         if (Count == 0)
  57.             throw new InvalidOperationException("Can't peak, heap is empty.");
  58.  
  59.         return items[0];
  60.     }
  61.  
  62.     public bool TryPeek(out T element)
  63.     {
  64.         if (Count == 0)
  65.         {
  66.             element = default;
  67.             return false;
  68.         }
  69.  
  70.         element = items[0];
  71.         return true;
  72.     }
  73.  
  74.     public T Extract()
  75.     {
  76.         if (Count == 0)
  77.             throw new InvalidOperationException("Can't pop, heap is empty.");
  78.         return ExtractInternal();
  79.     }
  80.  
  81.     public bool TryExtract(out T element)
  82.     {
  83.         if (Count == 0)
  84.         {
  85.             element = default;
  86.             return false;
  87.         }
  88.  
  89.         element = ExtractInternal();
  90.         return true;
  91.     }
  92.  
  93.     private T ExtractInternal()
  94.     {
  95.         T data = items[0];
  96.  
  97.         // Move and clear last element
  98.         int v = Count - 1;
  99.         items[0] = items[v];
  100.         items.RemoveAt(v);
  101.  
  102.         if (v != 0)
  103.             MoveDown();
  104.  
  105.         return data;
  106.     }
  107.  
  108.     private void MoveUp()
  109.     {
  110.         int index = items.Count - 1;
  111.         int parent = ParentOf(index);
  112.         while (!IsRoot(index) && items[index].CompareTo(items[parent]) < 0)
  113.         {
  114.             Swap(parent, index);
  115.             index = parent;
  116.             parent = ParentOf(index);
  117.         }
  118.     }
  119.  
  120.     private void MoveDown()
  121.     {
  122.         int index;
  123.         int parent = 0;
  124.         T item = items[parent];
  125.  
  126.         while (true)
  127.         {
  128.             int left = LeftChildOf(parent);
  129.             if (!ExistChild(left))
  130.                 break;
  131.  
  132.             int right = RightChildOf(parent);
  133.             if (!ExistChild(right))
  134.                 index = left;
  135.             else if (items[left].CompareTo(items[right]) < 0)
  136.                 index = left;
  137.             else
  138.                 index = right;
  139.  
  140.             Swap(index, parent);
  141.             parent = index;
  142.         }
  143.  
  144.         items[parent] = item;
  145.     }
  146.  
  147.     private bool ExistChild(int index) => index < Count;
  148.  
  149.     private bool IsRoot(int index) => index == 0;
  150.  
  151.     private void Swap(int a, int b)
  152.     {
  153.         T item = items[a];
  154.         items[a] = items[b];
  155.         items[b] = item;
  156.     }
  157.  
  158.     private int ParentOf(int index) => (index - 1) >> 1; // (index - 1) / 2
  159.  
  160.     private int LeftChildOf(int index) => (index << 1) + 1; // index * 2 + 1;
  161.  
  162.     private int RightChildOf(int index) => (index << 1) + 2; // index * 2 + 2;
  163. }
  164.  
RAW Paste Data