Class BinaryHeapBase<TKey, TValue>

Is a base class for Binary heap.

Inheritance

System.Object

BinaryHeapBase<TKey, TValue>

MaxBinaryHeap<TKey, TValue>

MinBinaryHeap<TKey, TValue>

MinMaxBinaryHeap<TKey, TValue>

MockBinaryHeap<TKey, TValue>

Implements

IBinaryHeap<TKey, TValue>

Inherited Members

System.Object.Equals(System.Object)

System.Object.Equals(System.Object, System.Object)

System.Object.GetHashCode()

System.Object.GetType()

System.Object.MemberwiseClone()

System.Object.ReferenceEquals(System.Object, System.Object)

System.Object.ToString()

Namespace: AlgorithmsAndDataStructures.DataStructures.BinaryHeaps.API

Assembly: AlgorithmsAndDataStructures.dll

Syntax

public abstract class BinaryHeapBase<TKey, TValue> : IBinaryHeap<TKey, TValue> where TKey : IComparable<TKey>

Type Parameters

Name	Description
TKey	The type of the keys stored in the heap.
TValue	The type of the values stored in the heap.

Constructors

| Improve this Doc View Source

BinaryHeapBase(List<KeyValuePair<TKey, TValue>>)

Constructor

Declaration

public BinaryHeapBase(List<KeyValuePair<TKey, TValue>> array)

Parameters

Type	Name	Description
System.Collections.Generic.List<System.Collections.Generic.KeyValuePair<TKey, TValue>>	array	The array containing all the key-values to be converted to a heap.

Fields

| Improve this Doc View Source

HeapArray

Declaration

public List<KeyValuePair<TKey, TValue>> HeapArray

Field Value

Type	Description
System.Collections.Generic.List<System.Collections.Generic.KeyValuePair<TKey, TValue>>	Is the array used to implement binary heap.

Methods

| Improve this Doc View Source

BubbleDown_Iteratively(Int32, Int32)

Implements the bubble down/trickle down operation using iteration.

Declaration

public abstract void BubbleDown_Iteratively(int rootIndex, int heapArrayLength)

Parameters

Type	Name	Description
System.Int32	rootIndex	The index of the root element, the element for which the trickle down should be performed.
System.Int32	heapArrayLength	The length of the heap array.

| Improve this Doc View Source

BubbleDown_Recursively(Int32, Int32)

Implements the bubble down/trickle down operation using recursion.

Declaration

public abstract void BubbleDown_Recursively(int rootIndex, int heapArrayLength)

Parameters

Type	Name	Description
System.Int32	rootIndex	The index of the root element, the element for which the trickle down should be performed.
System.Int32	heapArrayLength	The length of the heap array.

| Improve this Doc View Source

BubbleUp_Iteratively(Int32, Int32)

Moves the value in the given index, up in the heap till its position is found. The position is defined such to respect heap ordering property.

Declaration

public abstract void BubbleUp_Iteratively(int index, int heapArrayLength)

Parameters

Type	Name	Description
System.Int32	index	The index of the element that should be bubbled up.
System.Int32	heapArrayLength	The length/size of the heap array.

| Improve this Doc View Source

BuildHeap_Iteratively(Int32)

Note that passing the array size is not a must, as the class itself contains the array and has access to its size. However some algorithms such as HeapSort which rely on a heap to perform sorting, are better implemented, if we have the length of the array passed to these methods.

Declaration

public abstract void BuildHeap_Iteratively(int heapArrayLength)

Parameters

Type	Name	Description
System.Int32	heapArrayLength	The length of the heap array.

| Improve this Doc View Source

BuildHeap_Recursively(Int32)

Builds a heap using recursion, and does so in situ.

Declaration

public abstract void BuildHeap_Recursively(int heapArrayLength)

Parameters

Type	Name	Description
System.Int32	heapArrayLength	The length of the heap array.

| Improve this Doc View Source

FindIndex(TKey)

Find the index of a key in the heap array.

Declaration

public int FindIndex(TKey key)

Parameters

Type	Name	Description
TKey	key	A key for which the index in the array must be found.

Returns

Type	Description
System.Int32	The array index of the `key` if it exists and -1 otherwise.

| Improve this Doc View Source

GetLeftChildIndexInHeapArray(Int32)

Given a node index in the heapArray, returns the expected index of its left child.

Declaration

public int GetLeftChildIndexInHeapArray(int index)

Parameters

Type	Name	Description
System.Int32	index	The index of the node for which, left child index shall be found.

Returns

Type	Description
System.Int32	The index of the left child.

| Improve this Doc View Source

GetNodeLevel(Int32)

Returns the level of a node in the heap, given the node's index in the heap array.

Declaration

public int GetNodeLevel(int index)

Parameters

Type	Name	Description
System.Int32	index	The index of a node in an array.

Returns

Type	Description
System.Int32	Returns the level of the node.

| Improve this Doc View Source

GetParentIndex(Int32)

Given a node index in the heapArray, returns the expected index of its parent.

Declaration

public int GetParentIndex(int index)

Parameters

Type	Name	Description
System.Int32	index	The index of the node, for which parent index shall be found.

Returns

Type	Description
System.Int32	The index of the parent.

| Improve this Doc View Source

GetRightChildIndexInHeapArray(Int32)

Given a node index in the heapArray, returns the expected index of its right child.

Declaration

public int GetRightChildIndexInHeapArray(int index)

Parameters

Type	Name	Description
System.Int32	index	The index of the node for which, right child index shall be found.

Returns

Type	Description
System.Int32	The index of the right child.

| Improve this Doc View Source

Insert(KeyValuePair<TKey, TValue>, Int32)

Inserts a new value into heap.

Declaration

public abstract void Insert(KeyValuePair<TKey, TValue> keyValue, int heapArrayLength)

Parameters

Type	Name	Description
System.Collections.Generic.KeyValuePair<TKey, TValue>	keyValue	The key-value to be inserted into the heap.
System.Int32	heapArrayLength	The length of the heap array.

| Improve this Doc View Source

TryFindIndexOfMaxBiggerThanReference(List<KeyValuePair<TKey, TValue>>, Int32, List<Int32>, TKey, out Int32)

Finds the maximum element in the array, among the given indexes, with respect to maxValueReference, and returns the index of the max value.

Declaration

public bool TryFindIndexOfMaxBiggerThanReference(List<KeyValuePair<TKey, TValue>> list, int listLength, List<int> indexes, TKey maxKeyReference, out int maxKeyIndex)

Parameters

Type	Name	Description
System.Collections.Generic.List<System.Collections.Generic.KeyValuePair<TKey, TValue>>	list	The list of values.
System.Int32	listLength	The length of values array, which based on the usage, might be less than values.Count. For example when called via Heap-Sort.
System.Collections.Generic.List<System.Int32>	indexes	The list of indexes among which we want to find the maximum value.
TKey	maxKeyReference	The reference for the maximum value.
System.Int32	maxKeyIndex	The index of the maximum value among the specifies indexes.

Returns

Type	Description
System.Boolean	True in case of success, and false in case of failure.

| Improve this Doc View Source

TryFindIndexOfMinSmallerThanReference(List<KeyValuePair<TKey, TValue>>, List<Int32>, TKey, out Int32)

Finds the minimum element in the array, among the given indexes, with respect to minValueReference, and returns the index of the min value.

Declaration

public bool TryFindIndexOfMinSmallerThanReference(List<KeyValuePair<TKey, TValue>> list, List<int> indexes, TKey minKeyReference, out int minKeyIndex)

Parameters

Type	Name	Description
System.Collections.Generic.List<System.Collections.Generic.KeyValuePair<TKey, TValue>>	list	The list of values.
System.Collections.Generic.List<System.Int32>	indexes	The list of indexes among which we want to find the minimum value.
TKey	minKeyReference	The reference for the minimum value.
System.Int32	minKeyIndex	The index of the minimum value among the specifies indexes.

Returns

Type	Description
System.Boolean	True in case of success, and false in case of failure.

| Improve this Doc View Source

TryFindRoot(out KeyValuePair<TKey, TValue>, Int32)

Finds the root of the heap, without removing it.

Declaration

public abstract bool TryFindRoot(out KeyValuePair<TKey, TValue> keyValue, int heapArrayLength)

Parameters

Type	Name	Description
System.Collections.Generic.KeyValuePair<TKey, TValue>	keyValue	The key-value of the root.
System.Int32	heapArrayLength	The length of the heap array.

Returns

Type	Description
System.Boolean	True in case of success, and false in case of failure.

| Improve this Doc View Source

TryRemoveRoot(out KeyValuePair<TKey, TValue>, Int32)

Removes the root of the heap. In a MinHeap and MinMaxHeap this is the min, and in a MaxHeap and MaxMinHeap this is the max.

Declaration

public abstract bool TryRemoveRoot(out KeyValuePair<TKey, TValue> keyValue, int heapArrayLength)

Parameters

Type	Name	Description
System.Collections.Generic.KeyValuePair<TKey, TValue>	keyValue	The key-value of the root.
System.Int32	heapArrayLength	The length of the heap array.

Returns

Type	Description
System.Boolean	True in case of success, and false otherwise.

Implements

IBinaryHeap<TKey, TValue>