Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
MinHeap Class Reference

Public Member Functions

 MinHeap (int cap)
 
void MinHeapify (int)
 
int parent (int i)
 
int left (int i)
 
int right (int i)
 
int extractMin ()
 
void decreaseKey (int i, int new_val)
 
int getMin ()
 
void deleteKey (int i)
 
void insertKey (int k)
 

Private Attributes

int * harr
 pointer to array of elements in heap
 
int capacity
 maximum possible size of min heap
 
int heap_size
 Current number of elements in min heap.
 

Detailed Description

A class for Min Heap

Constructor & Destructor Documentation

◆ MinHeap()

MinHeap::MinHeap ( int  cap)
inlineexplicit

Constructor: Builds a heap from a given array a[] of given size

Parameters
[in]capacityinitial heap capacity
19  {
20  heap_size = 0;
21  capacity = cap;
22  harr = new int[cap];
23  }

Member Function Documentation

◆ decreaseKey()

void MinHeap::decreaseKey ( int  i,
int  new_val 
)

Decreases key value of key at index i to new_val

Decreases value of key at index 'i' to new_val. It is assumed that new_val is smaller than harr[i].

76  {
77  harr[i] = new_val;
78  while (i != 0 && harr[parent(i)] > harr[i]) {
79  std::swap(harr[i], harr[parent(i)]);
80  i = parent(i);
81  }
82 }
Here is the call graph for this function:

◆ deleteKey()

void MinHeap::deleteKey ( int  i)

Deletes a key stored at index i

This function deletes key at index i. It first reduced value to minus infinite, then calls extractMin()

105  {
106  decreaseKey(i, INT_MIN);
107  extractMin();
108 }
Here is the call graph for this function:

◆ extractMin()

int MinHeap::extractMin ( )

to extract the root which is the minimum element

85  {
86  if (heap_size <= 0)
87  return INT_MAX;
88  if (heap_size == 1) {
89  heap_size--;
90  return harr[0];
91  }
92 
93  // Store the minimum value, and remove it from heap
94  int root = harr[0];
95  harr[0] = harr[heap_size - 1];
96  heap_size--;
97  MinHeapify(0);
98 
99  return root;
100 }

◆ getMin()

int MinHeap::getMin ( )
inline

Returns the minimum key (key at root) from min heap

43 { return harr[0]; }

◆ insertKey()

void MinHeap::insertKey ( int  k)

Inserts a new key 'k'

55  {
56  if (heap_size == capacity) {
57  std::cout << "\nOverflow: Could not insertKey\n";
58  return;
59  }
60 
61  // First insert the new key at the end
62  heap_size++;
63  int i = heap_size - 1;
64  harr[i] = k;
65 
66  // Fix the min heap property if it is violated
67  while (i != 0 && harr[parent(i)] > harr[i]) {
68  std::swap(harr[i], harr[parent(i)]);
69  i = parent(i);
70  }
71 }
Here is the call graph for this function:

◆ left()

int MinHeap::left ( int  i)
inline

to get index of left child of node at index i

31 { return (2 * i + 1); }

◆ MinHeapify()

void MinHeap::MinHeapify ( int  i)

to heapify a subtree with the root at given index

A recursive method to heapify a subtree with the root at given index This method assumes that the subtrees are already heapified

113  {
114  int l = left(i);
115  int r = right(i);
116  int smallest = i;
117  if (l < heap_size && harr[l] < harr[i])
118  smallest = l;
119  if (r < heap_size && harr[r] < harr[smallest])
120  smallest = r;
121  if (smallest != i) {
122  std::swap(harr[i], harr[smallest]);
123  MinHeapify(smallest);
124  }
125 }
Here is the call graph for this function:

◆ right()

int MinHeap::right ( int  i)
inline

to get index of right child of node at index i

34 { return (2 * i + 2); }

The documentation for this class was generated from the following file:
MinHeap::heap_size
int heap_size
Current number of elements in min heap.
Definition: binaryheap.cpp:13
MinHeap::decreaseKey
void decreaseKey(int i, int new_val)
Definition: binaryheap.cpp:76
MinHeap::capacity
int capacity
maximum possible size of min heap
Definition: binaryheap.cpp:12
std::cout
MinHeap::harr
int * harr
pointer to array of elements in heap
Definition: binaryheap.cpp:11
MinHeap::MinHeapify
void MinHeapify(int)
Definition: binaryheap.cpp:113
MinHeap::left
int left(int i)
Definition: binaryheap.cpp:31
std::swap
T swap(T... args)
MinHeap::extractMin
int extractMin()
Definition: binaryheap.cpp:85
MinHeap::right
int right(int i)
Definition: binaryheap.cpp:34