Skip to content

Instantly share code, notes, and snippets.

@chandermani
Created May 26, 2021 18:40
Show Gist options
  • Save chandermani/d05c6d980bb5706acadf8e3382f03373 to your computer and use it in GitHub Desktop.
Save chandermani/d05c6d980bb5706acadf8e3382f03373 to your computer and use it in GitHub Desktop.
C# heap implementation
using System;
using System.Collections.Generic;
using System.Text;
namespace DataStructures
{
public class Heap<T>
{
private T[] items;
private int size;
private readonly Comparison<T> comparer;
public int Size => size;
public bool Empty => Size == 0;
public Heap(int capacity, Comparison<T> comparer)
{
items = new T[capacity];
size = 0;
this.comparer = comparer;
}
private bool LeftHasPriority(int left, int right)
{
return comparer(items[left], items[right]) < 0;
}
private int PushUp(int index)
{
if (index >= size || index < 0)
{
return index;
}
var parent = (index - 1) / 2;
while (parent >= 0 && parent != index && LeftHasPriority(index, parent))
{
// swap item at index and parent item
var temp = items[index];
items[index] = items[parent];
items[parent] = temp;
index = parent;
parent = (index - 1) / 2;
}
return index;
}
private void Heapify(int index)
{
if (index >= size || index < 0)
{
return;
}
while (true)
{
var left = 2 * index + 1;
var right = 2 * index + 2;
var first = index;
if (left < size && LeftHasPriority(left, first))
{
first = left;
}
if (right < size && LeftHasPriority(right, first))
{
first = right;
}
if (first == index)
{
break;
}
// swap index and first
var temp = items[index];
items[index] = items[first];
items[first] = temp;
index = first;
}
}
public T Peek()
{
if (size == 0)
{
return default(T);
}
return items[0];
}
private void RemoveAt(int index)
{
items[index] = items[--size];
items[size] = default(T);
if (PushUp(index) == index)
{
Heapify(index);
}
if (size < items.Length / 4)
{
var temp = items;
items = new T[items.Length / 2];
Array.Copy(temp, 0, items, 0, size);
}
}
public T Extract()
{
var result = Peek();
RemoveAt(0);
return result;
}
public void Add(T item)
{
if (size >= items.Length)
{
var temp = items;
items = new T[items.Length * 2];
Array.Copy(temp, items, temp.Length);
}
items[size] = item;
size++;
PushUp(size - 1);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment