Option Explicit On
Option Strict   On
Option Compare  Binary
Option Infer    On

Imports System
Imports System.Collections.Generic

	Class BHItem(Of T)
		Public Node  As BHNode(Of T)
		Public Value As T
	End Class

	Class BHNode(Of T)
		Public Parent  As BHNode(Of T)
		Public Sibling As BHNode(Of T)
		Public Child   As BHNode(Of T)
		Public Item    As BHItem(Of T)
	End Class

	Class BinHeap(Of T)
		Dim cmp   As Comparison(Of T)
		Dim Nodes As New List(Of BHNode(Of T))()
		Dim _Count As Integer
		Public Sub New(_cmp As Comparison(Of T))
			cmp = _cmp
		End Sub
		Public ReadOnly Property Count As Integer
			Get
				Return _Count
			End Get
		End Property
		Private Sub PushNode(ByVal node As BHNode(Of T), ByVal p As Integer)
			Do
				If p = Nodes.Count Then
					Nodes.Add(node)
					Exit Do
				ElseIf Nodes(p) Is Nothing Then
					Nodes(p) = node
					Exit Do
				Else
					If cmp(Nodes(p).Item.Value, node.Item.Value) < 0 Then
						node.Parent = Nodes(p)
						node.Sibling = Nodes(p).Child
						Nodes(p).Child = node
						node = Nodes(p)
					Else
						Nodes(p).Parent = node
						Nodes(p).Sibling = node.Child
						node.Child = Nodes(p)
					End If
					Nodes(p) = Nothing
					p += 1
				End If
			Loop
		End Sub
		Public Function Push(Value As T) As BHItem(Of T)
			Dim node As New BHNode(Of T)()
			Dim item As New BHItem(Of T)()
			item.Node = node
			item.Value = Value
			node.Item = item
			Dim p As Integer = 0
			Call PushNode(node, p)
			_Count += 1
			Push = item
		End Function
		Public Function Pop() As T
			Dim p As Integer = -1
			For i As Integer = 0 To Nodes.Count - 1
				If Nodes(i) Is Nothing Then Continue For
				If p >= 0 AndAlso cmp(Nodes(p).Item.Value, Nodes(i).Item.Value) < 0 Then
					Continue For
				End If
				p = i
			Next i
			Dim node  As BHNode(Of T) = Nodes(p)
			Dim child As BHNode(Of T) = node.Child
			Dim item  As BHItem(Of T) = node.Item
			node.Item = Nothing
			node.Child = Nothing
			item.Node = Nothing
			Nodes(p) = Nothing
			Do While child IsNot Nothing
				p -= 1
				node = child.Sibling
				child.Parent  = Nothing
				child.Sibling = Nothing
				Call PushNode(child, p)
				child = node
			Loop
			_Count -= 1
			Pop = item.Value
		End Function
		Private Sub SwapChild(node As BHNode(Of T))
			Dim selChild As BHNode(Of T) = node.Child
			Do While selChild IsNot Nothing
				Dim child As BHNode(Of T) = selChild.Sibling
				Do While child IsNot Nothing
					If cmp(child.Item.Value, selChild.Item.Value) < 0 Then
						selChild = child
					End If
					child = child.Sibling
				Loop
				If cmp(node.Item.Value, selChild.Item.Value) <= 0 Then
					Exit Sub
				End If
				Dim item As BHItem(Of T) = node.Item
				node.Item = selChild.Item
				node.Item.Node = node
				selChild.Item = item
				item.Node = selChild
				node = selChild
				selChild = node.Child
			Loop
		End Sub
		Private Sub SwapParent(node As BHNode(Of T))
			Dim parent As BHNode(Of T) = node.Parent
			Do While parent IsNot Nothing
				If cmp(parent.Item.Value, node.Item.Value) < 0 Then
					Exit Do
				End If
				Dim item As BHItem(Of T) = node.Item
				node.Item = parent.Item
				node.Item.Node = node
				parent.Item = item
				item.Node = parent
				node = parent
				parent = node.parent
			Loop
		End Sub
		Public Function Update(item As BHItem(Of T), newValue As T) As BHItem(Of T)
			item = item.Node.Item
			Dim oldValue As T = item.Value
			item.Value = newValue
			If cmp(oldValue, newValue) < 0 Then
				Call SwapChild(item.Node)
			Else
				Call SwapParent(item.Node)
			End If
			Update = item
		End Function
	End Class