Skip to content

Instantly share code, notes, and snippets.

@MaxWellHays
Created October 27, 2020 19:17
Show Gist options
  • Save MaxWellHays/b638245b757170e51669c48f295eaaef to your computer and use it in GitHub Desktop.
Save MaxWellHays/b638245b757170e51669c48f295eaaef to your computer and use it in GitHub Desktop.
C# Heap implementation
using System;
using System.Collections.Generic;
public class Heap<T>
{
List<T> a = new List<T>();
Comparer<T> comparer;
public Heap(Comparer<T> comparer)
{
this.comparer = comparer;
}
public Heap(Comparison<T> comparison)
{
this.comparer = Comparer<T>.Create(comparison);
}
public Heap()
{
this.comparer = Comparer<T>.Default;
}
public void Add(T value)
{
a.Add(value);
HeapifyUp(a.Count - 1);
}
public T PeekTop()
{
return a[0];
}
public T PopTop()
{
var result = PeekTop();
Swap(0, a.Count - 1);
a.RemoveAt(a.Count - 1);
HeapifyDown(0);
return result;
}
public void Remove(T value)
{
if (a[a.Count - 1].Equals(value))
{
a.RemoveAt(a.Count - 1);
return;
}
var index = a.IndexOf(value);
Swap(index, a.Count - 1);
a.RemoveAt(a.Count - 1);
int parentIndex = (index - 1) / 2;
if (comparer.Compare(a[index], a[parentIndex]) > 0)
{
HeapifyUp(index);
}
else
{
HeapifyDown(index);
}
}
public int Count => a.Count;
private void HeapifyUp(int index)
{
while (index > 0)
{
int parentIndex = (index - 1) / 2;
if (comparer.Compare(a[index], a[parentIndex]) > 0)
{
Swap(index, parentIndex);
index = parentIndex;
}
else
{
break;
}
}
}
private void HeapifyDown(int index)
{
while (true)
{
var leftChildIndex = index * 2 + 1;
if (leftChildIndex >= a.Count)
{
return;
}
var bestChildIndex = leftChildIndex;
var rightChildIndex = index * 2 + 2;
if (rightChildIndex < a.Count)
{
if (comparer.Compare(a[rightChildIndex], a[leftChildIndex]) > 0)
{
bestChildIndex = rightChildIndex;
}
}
if (comparer.Compare(a[bestChildIndex], a[index]) > 0)
{
Swap(bestChildIndex, index);
index = bestChildIndex;
}
else
{
break;
}
}
}
private void Swap(int i, int j)
{
var t = a[i];
a[i] = a[j];
a[j] = t;
}
}
public static class MaxHeap
{
public static Heap<T> Create<T>()
{
return new Heap<T>();
}
public static Heap<T> Create<T>(Func<T, int> keySelector)
{
Comparison<T> comparison = (x, y) => keySelector(x) - keySelector(y);
return new Heap<T>(comparison);
}
public static Heap<T> Create<T, Key>(Func<T, Key> keySelector, Comparer<Key> keyComparer)
{
Comparison<T> comparison = (x, y) => keyComparer.Compare(keySelector(x), keySelector(y));
return new Heap<T>(comparison);
}
public static Heap<T> Create<T, Key>(Func<T, Key> keySelector, Comparison<Key> keyComparer)
{
Comparison<T> comparison = (x, y) => keyComparer(keySelector(x), keySelector(y));
return new Heap<T>(comparison);
}
public static Heap<T> Create<T, Key>(Func<T, Key> keySelector)
{
Comparison<T> comparison = (x, y) => Comparer<Key>.Default.Compare(keySelector(x), keySelector(y));
return new Heap<T>(comparison);
}
public static Heap<T> Create<T>(Comparer<T> comparer)
{
return new Heap<T>(comparer);
}
public static Heap<T> Create<T>(Comparison<T> comparison)
{
return new Heap<T>(comparison);
}
}
public static class MinHeap
{
public static Heap<T> Create<T>()
{
return new Heap<T>((x, y) => Comparer<T>.Default.Compare(y, x));
}
public static Heap<T> Create<T>(Func<T, int> keySelector)
{
Comparison<T> comparison = (x, y) => keySelector(y) - keySelector(x);
return new Heap<T>(comparison);
}
public static Heap<T> Create<T>(Comparison<T> comparison)
{
return new Heap<T>((x, y) => comparison(y, x));
}
}
using System;
using System.Collections.Generic;
public class IndexedHeap<T> {
List<Record> a = new List<Record>();
Dictionary<T, int> dict = new Dictionary<T, int>();
Comparer<T> comparer;
int count;
public IndexedHeap(Comparer<T> comparer) {
this.comparer = comparer;
}
public IndexedHeap(Comparison<T> comparison) {
this.comparer = Comparer<T>.Create(comparison);
}
public IndexedHeap() {
this.comparer = Comparer<T>.Default;
}
public void Add(T value) {
if (dict.TryGetValue(value, out var index)) {
a[index].IncrementCount();
count++;
return;
}
a.Add(new Record(value));
count++;
dict[value] = a.Count - 1;
HeapifyUp(a.Count - 1);
}
public T PeekTop() {
return a[0].Value;
}
public T PopTop() {
var result = a[0];
result.DecrementCount();
count--;
if (result.Count > 0) {
return result.Value;
}
Swap(0, a.Count - 1);
a.RemoveAt(a.Count - 1);
dict.Remove(result.Value);
HeapifyDown(0);
return result.Value;
}
public bool Remove(T value) {
var lastRecord = a[a.Count - 1];
if (lastRecord.Value.Equals(value) && lastRecord.Count == 1) {
a.RemoveAt(a.Count - 1);
dict.Remove(value);
count--;
return true;
}
if (!dict.TryGetValue(value, out var index)) {
return false;
}
a[index].DecrementCount();
count--;
if (a[index].Count > 0) {
return true;
}
Swap(index, a.Count - 1);
a.RemoveAt(a.Count - 1);
dict.Remove(value);
int parentIndex = (index - 1) / 2;
if (comparer.Compare(a[index].Value, a[parentIndex].Value) > 0) {
HeapifyUp(index);
}
else {
HeapifyDown(index);
}
return true;
}
public int Count => count;
private void HeapifyUp(int index) {
while (index > 0) {
int parentIndex = (index - 1) / 2;
if (comparer.Compare(a[index].Value, a[parentIndex].Value) > 0) {
Swap(index, parentIndex);
index = parentIndex;
}
else {
break;
}
}
}
private void HeapifyDown(int index)
{
while (true) {
var leftChildIndex = index * 2 + 1;
if (leftChildIndex >= a.Count) {
return;
}
var bestChildIndex = leftChildIndex;
var rightChildIndex = index * 2 + 2;
if (rightChildIndex < a.Count) {
if (comparer.Compare(a[rightChildIndex].Value, a[leftChildIndex].Value) > 0) {
bestChildIndex = rightChildIndex;
}
}
if (comparer.Compare(a[bestChildIndex].Value, a[index].Value) > 0) {
Swap(bestChildIndex, index);
index = bestChildIndex;
}
else {
break;
}
}
}
private void Swap(int i, int j) {
var t = a[i];
a[i] = a[j];
a[j] = t;
dict[a[i].Value] = i;
dict[a[j].Value] = j;
}
IEnumerable<T> GetValues() {
foreach (var record in a) {
for (int i = 0; i < record.Count; i++) {
yield return record.Value;
}
}
}
private class Record {
public Record(T value) {
Value = value;
Count = 1;
}
public T Value;
public int Count;
public void IncrementCount() {
this.Count++;
}
public void DecrementCount() {
this.Count--;
}
}
}
public static class MaxIndexedHeap {
public static IndexedHeap<T> Create<T>(Func<T, int> keySelector) {
Comparison<T> comparison = (x, y) => keySelector(x) - keySelector(y);
return new IndexedHeap<T>(comparison);
}
}
public static class MinIndexedHeap {
public static IndexedHeap<T> Create<T>(Func<T, int> keySelector) {
Comparison<T> comparison = (x, y) => keySelector(y) - keySelector(x);
return new IndexedHeap<T>(comparison);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment