一种二叉堆的泛化实现

本文列出了一种二叉堆的泛化实现方法

所谓二叉堆,其实就是一种完全二叉树或者近似完全二叉树,树中 父节点的键值总是保持某种固定的序关系于任何一个子节点的键值 ,且每个节点的 左子树 和 右子树 也都是 二叉堆 .

这里列出一种二叉堆的泛化实现方法,其中值得一提的地方有这么几处:

• 泛化数据类型,方法自然是使用泛型实现
• 泛化序关系的表达方式,传统的最大堆和最小堆实现一般就是直接使用数值的大小比较,泛化的方法则是使用泛型委托
• 实现了一种类似于空间划分的元素查找方法

完整的代码可以在 gist 上找到:

using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Collections.ObjectModel;

public class Heap<T> where T : IEquatable<T>
{	
	public static Heap<T> Build(IEnumerable<T> items, Func<T, T, bool> predicate)
	{
		var heap = new Heap<T>(predicate);
		
		if (items != null)
		{
		    var iter = items.GetEnumerator();
		    while (iter.MoveNext())
		    {
		    	var item = iter.Current;
		    	heap.Add(item);
		    }
		}
		
		return heap;
	}
	
	/*
	public static Heap<T> Build2(IEnumerable<T> items, Func<T, T, bool> predicate)
	{
		var heap = new Heap<T>(predicate);
		
		if (items != null)
		{
			heap.m_items.AddRange(items);
			var itemCountIndexBegin = heap.m_items.Count / 2;
			var itemCountIndexEnd = 1;
			for (int i = itemCountIndexBegin; i >= itemCountIndexEnd; --i)
			{
				// NOTE this requires Heapify() just do "down-heap" operation
				//      now Heapify() do both "up-heap" and "down-heap" operation
				heap.Heapify(i - 1);
			}
		}
		
		return heap;
	}
	*/
	
	Func<T, T, bool> m_predicate;
	List<T> m_items = new List<T>();
	
	public int Count
	{
		get
		{
			return m_items.Count;
		}
	}
	
	public ReadOnlyCollection<T> Items
	{
		get
		{
		    return m_items.AsReadOnly();
		}
	}
	
	public T this[int index]
	{
		get
		{
			return m_items[index];
		}
	}
	
	public Heap(Func<T, T, bool> predicate)
	{
		Debug.Assert(predicate != null);
		m_predicate = predicate;
	}
	
	int IndexOfRecur(T item, int itemIndex)
	{
		if (IsValidIndex(itemIndex))
		{
			if (!m_predicate(item, m_items[itemIndex]))
			{
				// not found
				return -1;
			}
			else
			{
				if (m_items[itemIndex].Equals(item))
				{
					return itemIndex;
				}
				else
				{
					var itemCountIndex = itemIndex + 1;
					var childCountIndexLeft = itemCountIndex * 2;
					var childIndexLeft = childCountIndexLeft - 1;
					
					var index = IndexOfRecur(item, childIndexLeft);
					if (index >= 0)
					{
						return index;
					}
					else
					{
						var childCountIndexRight = itemCountIndex * 2 + 1;
					    var childIndexRight = childCountIndexRight - 1;
						return IndexOfRecur(item, childIndexRight);
					}
				}
			}
		}
		
		// default return -1
		return -1;
	}
	
	// return -1 when not found(recur)
	public int IndexOf(T item)
	{
		return IndexOfRecur(item, 0);
	}
	
	// return -1 when not found(iterator)
	public int IndexOf2(T item)
	{
		return m_items.IndexOf(item);
	}
	
	public void Add(T item)
	{
		m_items.Add(item);
		Heapify(m_items.Count - 1);
	}
	
	public void Remove(T item)
	{
		var itemIndex = IndexOf(item);
		if (itemIndex >= 0)
		{
			Swap(itemIndex, m_items.Count - 1);
			m_items.RemoveAt(m_items.Count - 1);
			Heapify(itemIndex);
		}
	}
	
	public void RemoveAt(int itemIndex)
	{
		if (IsValidIndex(itemIndex))
		{
			Swap(itemIndex, m_items.Count - 1);
			m_items.RemoveAt(m_items.Count - 1);
			Heapify(itemIndex);
		}
	}
	
	public void Clear()
	{
		m_items.Clear();
	}
	
	bool IsValidIndex(int itemIndex)
	{
		return itemIndex >= 0 && itemIndex < m_items.Count;
	}
	
	void Swap(int index1, int index2)
	{
		if (IsValidIndex(index1) && IsValidIndex(index2))
		{
			var temp = m_items[index1];
			m_items[index1] = m_items[index2];
			m_items[index2] = temp;
		}
	}
	
	void Heapify(int itemIndex)
	{
		if (IsValidIndex(itemIndex))
		{
			var itemCountIndex = itemIndex + 1;
			
			// first check parent
			var parentCountIndex = itemCountIndex / 2;
			var parentIndex = parentCountIndex - 1;
			if (IsValidIndex(parentIndex) && !m_predicate(m_items[itemIndex], m_items[parentIndex]))
			{
				while (IsValidIndex(itemIndex) && IsValidIndex(parentIndex) && !m_predicate(m_items[itemIndex], m_items[parentIndex]))
				{
					Swap(itemIndex, parentIndex);
					
					// update index
					itemIndex = parentIndex;
					itemCountIndex = itemIndex + 1;
					parentCountIndex = itemCountIndex / 2;
			        parentIndex = parentCountIndex - 1;
				}
			}
			else
			{
				// then check child
				var childCountIndexLeft = itemCountIndex * 2;
				var childIndexLeft = childCountIndexLeft - 1;
				var childCountIndexRight = itemCountIndex * 2 + 1;
				var childIndexRight = childCountIndexRight - 1;
				
				while (IsValidIndex(childIndexLeft))
				{
					if (IsValidIndex(childIndexRight))
					{
						if (!m_predicate(m_items[childIndexLeft], m_items[itemIndex]) || !m_predicate(m_items[childIndexRight], m_items[itemIndex]))
						{
							if (!m_predicate(m_items[childIndexLeft], m_items[itemIndex]) && m_predicate(m_items[childIndexRight], m_items[itemIndex]))
							{
								Swap(childIndexLeft, itemIndex);
								
								itemIndex = childIndexLeft;
								itemCountIndex = childCountIndexLeft;
							}
							else if (m_predicate(m_items[childIndexLeft], m_items[itemIndex]) && !m_predicate(m_items[childIndexRight], m_items[itemIndex]))
							{
								Swap(childIndexRight, itemIndex);
								
								itemIndex = childIndexRight;
								itemCountIndex = childCountIndexRight;
							}
							else
							{
								if (m_predicate(m_items[childIndexLeft], m_items[childIndexRight]))
								{
									// left should be child
									Swap(childIndexRight, itemIndex);
								
									itemIndex = childIndexRight;
									itemCountIndex = childCountIndexRight;
								}
								else
								{
									// right should be child
									Swap(childIndexLeft, itemIndex);
								
									itemIndex = childIndexLeft;
									itemCountIndex = childCountIndexLeft;
								}
							}
						
							// update index
							childCountIndexLeft = itemCountIndex * 2;
							childIndexLeft = childCountIndexLeft - 1;
							childCountIndexRight = itemCountIndex * 2 + 1;
							childIndexRight = childCountIndexRight - 1;
						}
						else
						{
							// break since fit
							break;
						}
					}
					else
					{
						// right child is invalid, reach end
						if (!m_predicate(m_items[childIndexLeft], m_items[itemIndex]))
						{
							Swap(childIndexLeft, itemIndex);
						}
						
						// break since reach end
						break;
					}
				}
			}
		}
	}
}

参考资料

• 二叉堆

不出意外的话,这应该是 2019 新年之前的最后的一篇博文,来年继续吧~