1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

// Description: Inserts an element.
bool insert( ElementType ) ;
// Description: Removes the element located at the root and returns it.
// Precondition: Binary heap is not empty.
// Throws EmptyBinaryHeapException if binary heap is empty.
ElementType remove( );
// Description: Returns the element located at the root.
// Precondition: Binary heap is not empty.
// Postcondition: The binary heap is unchanged by this operation.
// Throws EmptyBinaryHeapException if binary heap is empty.
ElementType max( ) const;
ElementType min( ) const;
// Description: Returns the number of elements stored in the data collection.
// Postcondition: The binary heap is unchanged by this operation.
int getElementCount( ) const;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

indexOfRoot = 0
indexOfBottom = elementCount
insert new element @ “bottom” of heap(@ indexOfBottom)
elementCount++
reHeapUp(indexOfBottom)
// If the element has a parent and …
if (indexOfBottom > indexOfRoot)
  indexOfParent = floor((indexOfBottom– 1) / 2)
// … key value of parent < key value of child then …
if (heap[indexOfParent] > heap[indexOfBottom])
  //… swap the element with its parent
  swap heap[indexOfParent] with heap[indexOfBottom]
reHeapUp(indexOfParent)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

int MinHeap::extractMin()
{
	if (heap_size <= 0)
		return INT_MAX;
	if (heap_size == 1)
	{
		heap_size--;
		return harr[0];
	}

	// Move last element to first then reHeapDown
	int root = harr[0];
	harr[0] = harr[heap_size-1];
	heap_size--;
	MinHeapify(0);

	return root;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

indexOfRoot = 0
indexOfBottom = elementCount
insert new element @“ bottom” of heap(@ indexOfBottom)
elementCount++
reHeapUp(indexOfBottom)
// If the element has a parent and …
if (indexOfBottom > indexOfRoot)
  indexOfParent = floor((indexOfBottom– 1) / 2)
// … key value of parent < key value of child then …
if (heap[indexOfParent] < heap[indexOfBottom])
  //… swap the element with its parent
  swap heap[indexOfParent] with heap[indexOfBottom]
reHeapUp(indexOfParent)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

indexOfRoot = 0
call retrieve()(optional) =>
  return element stored in root of heap(array[indexOfRoot])
replace element stored in root with element stored at the bottom of
  heap i.e., last element => copy element stored at the bottom(at index elementCount - 1)
into root of heap => elementCount–
reHeapDown(indexOfRoot)
// If the parent has at least a child and …
if (heap[indexOfRoot] is not a leaf)
  compute index of children
compare the children and pick largest child
set indexOfMaxChild to index of largest child of root
// … key value of parent < key value of largest child then …
if (heap[indexOfRoot] < heap[indexOfMaxChild])
  //… swap the parent with its largest child
  swap heap[indexOfRoot] with heap[indexOfMaxChild]
reHeapDown(indexOfMaxChild)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

// Utility method - Recursively put the array back into a min Binary Heap.
template <class ElementType>
void BinaryHeap<ElementType>::reHeapUp(unsigned int indexOfBottom) {

	if(indexOfBottom > 0) {
		int indexOfParent = floor((indexOfBottom - 1) / 2);
		if(elements[indexOfBottom] <= elements[indexOfParent])
		{
			//Swap
			ElementType temp = elements[indexOfParent];
			elements[indexOfParent] = elements[indexOfBottom];
			elements[indexOfBottom] = temp;
			reHeapUp(indexOfParent);
		}
	}

	return;
	
} // end reHeapUp
#### reHeapDown
```cpp
template <class ElementType>
void BinaryHeap<ElementType>::reHeapDown(unsigned int indexOfRoot) {

	unsigned int indexOfMinChild = indexOfRoot;
	
	// Find indices of children.
	unsigned int indexOfLeftChild = 2*indexOfRoot+1;
	unsigned int indexOfRightChild = 2*indexOfRoot+2;

    // Base case: elements[indexOfRoot] is a leaf as it has no children
	if (indexOfLeftChild > elementCount-1) return;

	// If we need to swap, select the smallest child
    if (elements[indexOfRoot] > elements[indexOfLeftChild])
    	indexOfMinChild = indexOfLeftChild;

    // Check if there is a right child, is it the smallest?
    if (indexOfRightChild < elementCount) {
		if (elements[indexOfMinChild] > elements[indexOfRightChild])
		    indexOfMinChild = indexOfRightChild;
	}

	// Swap parent with smallest of children.
	if (indexOfMinChild != indexOfRoot) {
		
	   ElementType temp = elements[indexOfRoot];
	   elements[indexOfRoot] = elements[indexOfMinChild];
	   elements[indexOfMinChild] = temp;
	   
	   // Recursively put the array back into a heap
	   reHeapDown(indexOfMinChild);
    }

	return;
	
} // end reHeapDown
___
References:

Created:: 2022-03-14 05:29