|
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.
|
|
◆ MinHeap()
MinHeap::MinHeap |
( |
int | cap | ) |
|
|
inlineexplicit |
Constructor: Builds a heap from a given array a[] of given size
- Parameters
-
[in] | capacity | initial heap capacity |
19 {
23 }
int * harr
pointer to array of elements in heap
Definition binaryheap.cpp:11
int capacity
maximum possible size of min heap
Definition binaryheap.cpp:12
int heap_size
Current number of elements in min heap.
Definition binaryheap.cpp:13
◆ ~MinHeap()
◆ 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 {
78 while (i != 0 &&
harr[parent(i)] >
harr[i]) {
80 i = parent(i);
81 }
82}
◆ 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 {
108}
int extractMin()
Definition binaryheap.cpp:85
void decreaseKey(int i, int new_val)
Definition binaryheap.cpp:76
◆ extractMin()
int MinHeap::extractMin |
( |
| ) |
|
to extract the root which is the minimum element
85 {
87 return INT_MAX;
91 }
92
93
98
99 return root;
100}
void MinHeapify(int)
Definition binaryheap.cpp:113
◆ getMin()
Returns the minimum key (key at root) from min heap
◆ insertKey()
void MinHeap::insertKey |
( |
int | k | ) |
|
Inserts a new key 'k'
55 {
57 std::cout <<
"\nOverflow: Could not insertKey\n";
58 return;
59 }
60
61
65
66
67 while (i != 0 &&
harr[parent(i)] >
harr[i]) {
69 i = parent(i);
70 }
71}
double k(double x)
Another test function.
Definition composite_simpson_rule.cpp:117
◆ 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 {
116 int smallest = i;
120 smallest = r;
121 if (smallest != i) {
124 }
125}
int left(int i)
Definition binaryheap.cpp:31
int right(int i)
Definition binaryheap.cpp:34
double l(double x)
Another test function.
Definition composite_simpson_rule.cpp:119
◆ parent()
int MinHeap::parent |
( |
int | i | ) |
|
|
inline |
28{ return (i - 1) / 2; }
◆ 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: