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]

capacity

initial heap capacity

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

~MinHeap()

MinHeap::~MinHeap ( )

inline

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

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

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

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

Here is the call graph for this function:

extractMin()

int MinHeap::extractMin

(

)

to extract the root which is the minimum element

                        {
    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

{ return harr[0]; }

insertKey()

void MinHeap::insertKey

(

int

k

)

Inserts a new key 'k'

                             {
    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);
    }
}

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

{ 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

                              {
    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);
    }
}

Here is the call graph for this function:

parent()

int MinHeap::parent ( int  i )

inline

{ return (i - 1) / 2; }

right()

int MinHeap::right ( int  i )

inline

to get index of right child of node at index i

{ return (2 * i + 2); }

---

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

• data_structures/binaryheap.cpp