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

Definition at line 10 of file binaryheap.cpp.

Constructor & Destructor Documentation

MinHeap()

MinHeap::MinHeap ( int cap )

inlineexplicit

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

Parameters

[in]

capacity

initial heap capacity

Definition at line 19 of file binaryheap.cpp.

                              {
        heap_size = 0;
        capacity = cap;
        harr = new int[cap];
    }

~MinHeap()

MinHeap::~MinHeap ( )

inline

Definition at line 51 of file binaryheap.cpp.

{ delete[] harr; }

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].

Definition at line 76 of file binaryheap.cpp.

                                            {
    harr[i] = new_val;
    while (i != 0 && harr[parent(i)] > harr[i]) {
        std::swap(harr[i], harr[parent(i)]);
        i = parent(i);
    }
}

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()

Definition at line 105 of file binaryheap.cpp.

                             {
    decreaseKey(i, INT_MIN);
    extractMin();
}

extractMin()

int MinHeap::extractMin

(

)

to extract the root which is the minimum element

Definition at line 85 of file binaryheap.cpp.

                        {
    if (heap_size <= 0)
        return INT_MAX;
    if (heap_size == 1) {
        heap_size--;
        return harr[0];
    }
 
    // Store the minimum value, and remove it from heap
    int root = harr[0];
    harr[0] = harr[heap_size - 1];
    heap_size--;
    MinHeapify(0);
 
    return root;
}

getMin()

int MinHeap::getMin ( )

inline

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

Definition at line 43 of file binaryheap.cpp.

{ return harr[0]; }

insertKey()

void MinHeap::insertKey

(

int

k

)

Inserts a new key 'k'

Definition at line 55 of file binaryheap.cpp.

                             {
    if (heap_size == capacity) {
        std::cout << "\nOverflow: Could not insertKey\n";
        return;
    }
 
    // First insert the new key at the end
    heap_size++;
    int i = heap_size - 1;
    harr[i] = k;
 
    // Fix the min heap property if it is violated
    while (i != 0 && harr[parent(i)] > harr[i]) {
        std::swap(harr[i], harr[parent(i)]);
        i = parent(i);
    }
}

left()

int MinHeap::left ( int i )

inline

to get index of left child of node at index i

Definition at line 31 of file binaryheap.cpp.

{ 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

Definition at line 113 of file binaryheap.cpp.

                              {
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l] < harr[i])
        smallest = l;
    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;
    if (smallest != i) {
        std::swap(harr[i], harr[smallest]);
        MinHeapify(smallest);
    }
}

parent()

int MinHeap::parent ( int i )

inline

Definition at line 28 of file binaryheap.cpp.

{ return (i - 1) / 2; }

right()

int MinHeap::right ( int i )

inline

to get index of right child of node at index i

Definition at line 34 of file binaryheap.cpp.

{ return (2 * i + 2); }

Member Data Documentation

capacity

int MinHeap::capacity

private

maximum possible size of min heap

Definition at line 12 of file binaryheap.cpp.

harr

int* MinHeap::harr

private

pointer to array of elements in heap

Definition at line 11 of file binaryheap.cpp.

heap_size

int MinHeap::heap_size

private

Current number of elements in min heap.

Definition at line 13 of file binaryheap.cpp.

---

The documentation for this class was generated from the following file:

• data_structures/binaryheap.cpp