Skip to content

Instantly share code, notes, and snippets.

@Vivek-abstract
Created July 5, 2023 14:36
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Vivek-abstract/1469db96d261088f984cb2b101699b38 to your computer and use it in GitHub Desktop.
Save Vivek-abstract/1469db96d261088f984cb2b101699b38 to your computer and use it in GitHub Desktop.
Min Heap and max heap implementation using C#
public class MinHeap
{
public List<int> Heap {get; set;}
public int Count {get; set;}
public MinHeap()
{
Heap = new();
}
public MinHeap(int[] nums)
{
Heap = new();
foreach(int num in nums)
{
Heap.Add(num);
Count++;
}
for(int i = nums.Length - 1; i >= 0; i--)
{
Heapify(i);
}
}
private void Heapify(int pos)
{
// Check if node and its children are correct heap
int leftPos = 2 * pos + 1;
int rightPos = 2 * pos + 2;
int leftChild = leftPos >= Count ? Int32.MaxValue : Heap[leftPos];
int rightChild = rightPos >= Count ? Int32.MaxValue : Heap[rightPos];
if(leftChild == Int32.MaxValue)
{
// If no left child then there is no right child
return;
}
int root = Heap[pos];
if(leftChild <= rightChild && root > leftChild)
{
// Swap left and root
Swap(leftPos, pos);
Heapify(leftPos);
}
else if(rightChild <= leftChild && root > rightChild)
{
// Swap right and root
Swap(rightPos, pos);
Heapify(rightPos);
}
}
public int PopMin()
{
int res = Heap[0];
Heap[0] = Heap[Count-1];
Count--;
Heapify(0);
return res;
}
public void Add(int val)
{
// Add at end i.e. Count and then heapify up
if(Count < Heap.Count)
{
Heap[Count] = val;
}
else
{
Heap.Add(val);
}
Count++;
int pos = Count - 1;
int parentPos = (int)Math.Floor((double)(pos - 1) / 2);
while(pos > 0)
{
if(Heap[pos] >= Heap[parentPos])
{
break;
}
Swap(pos, parentPos);
pos = parentPos;
parentPos = (int)Math.Floor((double)(pos - 1) / 2);
}
}
public int Peek()
{
return Heap[0];
}
private void Swap(int first, int second)
{
int tmp = Heap[first];
Heap[first] = Heap[second];
Heap[second] = tmp;
}
}
public class MaxHeap
{
public List<int> Heap {get; set;}
public int Count {get; set;}
public MaxHeap(int[] nums)
{
Heap = new();
foreach(int num in nums)
{
Heap.Add(num);
Count++;
}
for(int i = nums.Length; i>=0; i--)
{
Heapify(i);
}
}
private void Heapify(int pos)
{
int leftPos = 2 * pos + 1;
int rightPos = 2 * pos + 2;
while(leftPos < Count || rightPos < Count)
{
int leftChild = leftPos < Count ? Heap[leftPos] : Int32.MinValue;
int rightChild = rightPos < Count ? Heap[rightPos] : Int32.MinValue;
int root = Heap[pos];
if(leftChild >= rightChild && root < leftChild)
{
Swap(leftPos, pos);
pos = leftPos;
}
else if(rightChild >= leftChild && root < rightChild)
{
Swap(rightPos, pos);
pos = rightPos;
}
else
{
break;
}
leftPos = 2 * pos + 1;
rightPos = 2 * pos + 2;
}
}
public void Add(int val)
{
if(Count < Heap.Count)
{
Heap[Count] = val;
}
else
{
Heap.Add(val);
}
Count++;
int pos = Count - 1;
while(pos > 0)
{
int parentPos = (pos - 1) / 2;
if(Heap[pos] > Heap[parentPos])
{
Swap(pos, parentPos);
pos = parentPos;
}
else
{
break;
}
}
}
public int PopMax()
{
int res = Heap[0];
Heap[0] = Heap[Count-1];
Count--;
Heapify(0);
return res;
}
public int Peek()
{
return Heap[0];
}
private void Swap(int first, int second)
{
int tmp = Heap[first];
Heap[first] = Heap[second];
Heap[second] = tmp;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment