Max & Min Heap

So now that class is over and I took my final for my CS2420 class last night, I find that I have come to love programming and I miss not having an assignment to work on. So today I decided that since I had already created a Max Heap class, that I should also create a Min Heap class.

While I was working, I found that 99% of the code was going to be the same, and I didn't want to just create a copy and tweak a few lines. So instead I decided to create a abstract Heap class that I could inherit from.

So I created the base class and moved most of the code to that file. Then I made the Max and Min Heap classes and made the changes required in each class to make it work. While this also wasn't that hard, I think that it was a good exerciser. I did something similar in the Components assignment, but I think this was a much better example of how to use inheritance.

Here is my code:

	using System.Collections;
	using System.Collections.Generic;
	abstract class Heap<T> : IEnumerable<T>
	{
	protected T[] UnderlyingArray;
	protected int ElementCount = 0;
	protected int OldCount = 0;
	protected bool IsHeap = true;
	public int Count
	{
	get
	{
	return ElementCount;
	}
	}
	public void Clear()
	{
	UnderlyingArray = new T[UnderlyingArray.Length];
	}
	public T this[int index]
	{
	get
	{
	return UnderlyingArray[index];
	}
	}
	abstract public void Add(T new_value);
	abstract public void Sort();
	public void BuildHeap()
	{
	if (IsHeap)
	return;
	int last_item = OldCount - 1;
	for (int index = 0; index < OldCount / 2; index++)
	{
	Swap(index, last_item);
	last_item--;
	}
	ElementCount = OldCount;
	IsHeap = true;
	}
	protected void Swap(int first, int second)
	{
	T temp = UnderlyingArray[first];
	UnderlyingArray[first] = UnderlyingArray[second];
	UnderlyingArray[second] = temp;
	}
	protected int FindParent(int current_index)
	{
	return (current_index - 1) / 2;
	}
	protected int FindLeft(int current_index)
	{
	return (current_index * 2) + 1;
	}
	protected int FindRight(int current_index)
	{
	return (current_index * 2) + 2;
	}
	protected void Resize()
	{
	T[] new_array = new T[UnderlyingArray.Length * 2];
	for (int index = 0; index < UnderlyingArray.Length; index++)
	new_array[index] = UnderlyingArray[index];
	UnderlyingArray = new_array;
	}
	public IEnumerator<T> GetEnumerator()
	{
	for (int index = 0; index < ElementCount; index++)
	{
	T temp = UnderlyingArray[index];
	yield return temp;
	}
	}
	IEnumerator IEnumerable.GetEnumerator()
	{
	return GetEnumerator();
	}
	}

view raw Heap.cs hosted with ❤ by GitHub

	using System;
	class MaxHeap<T> : Heap<T> where T : IComparable
	{
	public MaxHeap()
	{
	UnderlyingArray = new T[5];
	}
	public MaxHeap(int starting_size)
	{
	UnderlyingArray = new T[starting_size];
	}
	public override void Add(T new_value)
	{
	if (!IsHeap)
	BuildHeap();
	if (ElementCount == UnderlyingArray.Length)
	Resize();
	UnderlyingArray[ElementCount] = new_value;
	Swim();
	ElementCount++;
	}
	public T PopMax()
	{
	if (!IsHeap)
	BuildHeap();
	T max = UnderlyingArray[0];
	Swap(0, ElementCount - 1);
	UnderlyingArray[ElementCount - 1] = default(T);
	ElementCount--;
	Sink();
	return max;
	}
	public override void Sort()
	{
	if (!IsHeap)
	BuildHeap();
	OldCount = ElementCount;
	for (int i = 0; i < OldCount; i++)
	{
	Swap(0, ElementCount - 1);
	ElementCount--;
	Sink();
	}
	IsHeap = false;
	ElementCount = OldCount;
	}
	private void Sink()
	{
	int current_index = 0;
	while (current_index < ElementCount)
	{
	int max_child = current_index;
	int left_child = FindLeft(current_index);
	int right_child = FindRight(current_index);
	if (left_child >= ElementCount)
	break;
	if (right_child >= ElementCount)
	max_child = left_child;
	if (right_child < ElementCount &&
	UnderlyingArray[left_child].CompareTo(UnderlyingArray[right_child]) == 0)
	max_child = left_child;
	if (right_child < ElementCount &&
	UnderlyingArray[left_child].CompareTo(UnderlyingArray[right_child]) > 0)
	max_child = left_child;
	if (right_child < ElementCount &&
	UnderlyingArray[left_child].CompareTo(UnderlyingArray[right_child]) < 0)
	max_child = right_child;
	if (UnderlyingArray[max_child].CompareTo(UnderlyingArray[current_index]) == 0)
	break;
	if (UnderlyingArray[max_child].CompareTo(UnderlyingArray[current_index]) > 0)
	Swap(current_index, max_child);
	current_index = max_child;
	}
	}
	private void Swim()
	{
	int current_index = ElementCount;
	while (current_index != 0)
	{
	int parent_index = FindParent(current_index);
	if (UnderlyingArray[current_index].CompareTo(UnderlyingArray[parent_index]) == 0)
	break;
	else if (UnderlyingArray[current_index].CompareTo(UnderlyingArray[parent_index]) > 0)
	Swap(current_index, parent_index);
	current_index = parent_index;
	}
	}
	}

view raw MaxHeap.cs hosted with ❤ by GitHub

	using System;
	class MinHeap<T> : Heap<T> where T : IComparable
	{
	public MinHeap(int starting_size)
	{
	UnderlyingArray = new T[starting_size];
	}
	public MinHeap()
	{
	UnderlyingArray = new T[5];
	}
	public override void Add(T new_value)
	{
	if (!IsHeap)
	BuildHeap();
	if (ElementCount == UnderlyingArray.Length)
	Resize();
	UnderlyingArray[ElementCount] = new_value;
	Swim();
	ElementCount++;
	}
	public T PopMin()
	{
	if (!IsHeap)
	BuildHeap();
	T max = UnderlyingArray[0];
	Swap(0, ElementCount - 1);
	UnderlyingArray[ElementCount - 1] = default(T);
	ElementCount--;
	Sink();
	return max;
	}
	public override void Sort()
	{
	if (!IsHeap)
	BuildHeap();
	OldCount = ElementCount;
	for (int i = 0; i < OldCount; i++)
	{
	Swap(0, ElementCount - 1);
	ElementCount--;
	Sink();
	}
	IsHeap = false;
	ElementCount = OldCount;
	}
	private void Sink()
	{
	int current_index = 0;
	while (current_index < ElementCount)
	{
	int smallest_child = current_index;
	int left_child = FindLeft(current_index);
	int right_child = FindRight(current_index);
	if (left_child >= ElementCount)
	break;
	if (right_child >= ElementCount)
	smallest_child = left_child;
	if (right_child < ElementCount &&
	UnderlyingArray[left_child].CompareTo(UnderlyingArray[right_child]) == 0)
	smallest_child = left_child;
	if (right_child < ElementCount &&
	UnderlyingArray[left_child].CompareTo(UnderlyingArray[right_child]) > 0)
	smallest_child = right_child;
	if (right_child < ElementCount &&
	UnderlyingArray[left_child].CompareTo(UnderlyingArray[right_child]) < 0)
	smallest_child = left_child;
	if (UnderlyingArray[smallest_child].CompareTo(UnderlyingArray[current_index]) == 0)
	break;
	if (UnderlyingArray[smallest_child].CompareTo(UnderlyingArray[current_index]) < 0)
	Swap(current_index, smallest_child);
	current_index = smallest_child;
	}
	}
	private void Swim()
	{
	int current_index = ElementCount;
	while (current_index != 0)
	{
	int parent_index = FindParent(current_index);
	if (UnderlyingArray[current_index].CompareTo(UnderlyingArray[parent_index]) == 0)
	break;
	else if (UnderlyingArray[current_index].CompareTo(UnderlyingArray[parent_index]) < 0)
	Swap(current_index, parent_index);
	current_index = parent_index;
	}
	}
	}

view raw MinHeap.cs hosted with ❤ by GitHub

That's all for now, thanks for reading!