Ternary Heap Sort Code in C++ using Heap Data structure

Introduction:

This code is implementation of ternary heap sort. The code requires no input. Data inputs (integers) are generated randomly then sorted using heap sort.

Only change the define SIZE value to for sorting large or small amount of numbers.

Code for Binary Heap Sort here.

Ternary Heap Sort Code Cpp:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Problem: Ternary Heap Sort
 */

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10
int A[SIZE], heapsize = SIZE;

void maxHeapify(int i){
    int largest;

    /**
     * Find right child index
     */
    int l = 3 * i + 1;

    /**
     * Compare left child against the current node
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * find mid child index
     */
    int m = 3 * i + 2;

    /**
     * Compare mid child against the calculated largest value node
     */
    if(m < heapsize && A[m] > A[largest])
        largest = m;

    /**
     * Find right child index
     */
    int r = 3 * i + 3;

    /**
     * Compare right child against the calculated largest value node
     */
    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /*
     * If child nodes have larger value then current node
     */
    if(largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    int j;
    /**
     * operate on third of array
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    int i;
    for(i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);

        /**
         * Decrease the heap size as right of heap is already sorted
         */
        --heapsize;

        /**
         * Again max heapify the rest of the heap
         */
        maxHeapify(0);
    }
}

int main(){
    int i;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for(i=0; i<SIZE; ++i){
        A[i] = rand() % SIZE;
        printf("%d ", A[i]);
    }
    printf("\n");

    printf("Sorting Now....\n");
    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i=0; i<SIZE; ++i)
        printf("%d ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}
Advertisements

Min Priority Queue Implementation Using Array Min Heap

Min Priority Queue Implementation Using Array Min Heap:

The code is explained in comments. This code is implementation of min / minimum priority queue using min heap.

An easy to follow priority queue theory tutorial ( Max Priority Queue, Max Heap ) and with visualizations can be found here.


 Min Priority Queue Implementation C++:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 * Code:    Min Priority Queue Implementation Using Array Min Heap
 */

#include<iostream>
#include<cstdio>
#include<climits>
#include<cmath>
using namespace std;

#define N 100

struct node{
    char data;
    int key;
} A[N];

/*
 * Initial heap size 0 as heap is empty
 */
int heapsize = 0;

/*
 * Find the parent node
 */
int parent(int i){
    return ceil(i / 2.0 - 1);
}

/*
 * Use for heap insert and decrease key
 * In if condition check if user attempted to increase value instead of decrease
 * Compare child with parent, if child is smaller then swap
 * Now mark that child and apply the same logic until it reaches root node
 */
void decreaseKey(int i, node n){
    if(n.key > A[i].key){
        printf("Error\n");
        return;
    }

    A[i] = n;
    while(i > 0 && A[parent(i)].key > A[i].key){
        std:: swap(A[i], A[parent(i)]);
        i = parent(i);
    }
}

/*
 * Search for a specific node to change its value
 * Returns the index the node being searched
 */
int searchIndex(node n){
    for(int i = 0; i < heapsize; ++i){
        if(A[i].data == n.data)
            return i;
    }
    return heapsize;
}

/*
 * Called initially to create a min heap
 * Also called after a node extraction from min heap
 * Since the smallest value node is at the root of min heap
 * After extraction min heapify is called on root node
 * It compares parent with its children
 * If a smaller child found then its swapped with parent and
 * Min heapify is again called on that child to apply same procedure
 */
void minHeapify(int i){
    int largest;

    int l = 2*i +1;

    if (l < heapsize && A[l].key < A[i].key)
        largest = l;
    else
        largest = i;

    int r = 2*i +2;

    if (r < heapsize && A[r].key < A[largest].key)
        largest = r;

    if (largest != i){
        std::swap(A[i], A[largest]);
        minHeapify(largest);
    }
}

/*
 * Does not extract any items only show the minimum element
 */
node heapMinimum(){
    return A[0];
}

/*
 * Increase heap size to create space for new node
 * Insert the node at that space by calling decrease key function
 */
void heapInsert(node n){
    ++heapsize;
    A[heapsize - 1].key = INT_MAX;
    decreaseKey(heapsize - 1, n);
}

/*
 * Heap size less than zero mean no items in heap so nothing to extract
 * For min heap minimum value is at the root which in here is A[0]
 * Save the root and replace root with last element in the heap and decrease the heap size
 * So the root is still in the array in last position but no longer in the heap
 * Since the last element is now the root the heap may be unbalanced
 * So to balance the heap call min heapify on the root node again
 * Lastly return the saved root
 */
node extractMin(){
    if(heapsize < 0)
        printf("Heap Underflow\n");

    node min = A[0];
    A[0] = A[heapsize - 1];
    --heapsize;
    minHeapify(0);
    return min;
}

/*
 * Every time we extract heap size is automatically reduced
 * So no need change heap size in while loop
 */
void printPriorityQueue(){
    printf("Main Output:\n");
    while(heapsize){
        node ext = extractMin();
        printf("%c %d\n", ext.data, ext.key );
    }
}

/*
 * input data and key for node and insert that node in min priority queue
 */
void inputQueueItems(){
    int i;
    printf("How many nodes?\n");
    scanf("%d", &i); getchar();
    while(i--){
        node n;
        printf("Enter node name and its value:\n");
        scanf("%c%d", &n.data, &n.key);
        getchar();
        heapInsert(n);
    }
}

int main(){

    inputQueueItems();
    printPriorityQueue();


    /*
     * Sample input for quick testing
     * Before using this comment inputQueueItems() function call
     */
    /*
    heapInsert({'z',99});
    heapInsert({'a',9});
    heapInsert({'v',29});
    heapInsert({'x',19});
    heapInsert({'c',95});
    heapInsert({'g',22});
    heapInsert({'b', 1});
    heapInsert({'e', 5});
    heapInsert({'d', 2});
    */
    //decreaseKey( searchIndex({'a', 9}), {'a', 4} );

    return 0;
}

Ternary Heap Sort Algorithm Implementation Using heap Data Structure

Ternary Heap Sort Algorithm Implementation Using heap Data Structure :


Ternary Heap Sort Algorithm Code:

#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<iostream>

#define SIZE 10000
long A[SIZE], heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find index of first, second, third child
     */
    long l = 3 * i + 1;
    long m = 3 * i + 2;
    long r = 3 * i + 3;

    /**
     * Find largest among the parent and its child. And save that index
     */
    if(l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    if(m < heapsize && A[m] > A[largest])
        largest = m;

    if(r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * If the largest index is not of parent then there is another bigger value
     * So swap that value with parent
     */
    if(largest != i){
        std::swap(A[i], A[largest]);
        maxHeapify(largest);
    }
}

void buildMaxHeap(){
    long j;
    /**
     * Starting from the last parent to root max heapify
     */
    for(j = heapsize / 3 - 1; j >= 0; --j)
        maxHeapify(j);
}

void heapsort(){
    buildMaxHeap();

    long i;
    /**
     * Send biggest value root in the end
     * then max heapify from root again
     * this procedure sorts in ascending order because of max heap
     */
    for(i = heapsize-1; i > 0; --i){
        std::swap(A[0], A[i]);

        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    register long i = 0;
    for(; i < SIZE; ++i){
        A[i] = rand() % SIZE;
        //printf("%ld ", A[i]);
    }
    //printf("\n");

    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}

Binary Heap Sort Algorithm Code Using Heap Data Structure

Binary Heap Sort Algorithm Code Using Heap Data Structure:


Binary Heap Sort Code:

/**
 * @author  Quickgrid ( Asif Ahmed )
 * @link    https://quickgrid.wordpress.com
 */

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<ctime>

#define SIZE 10000
long A[SIZE];

/**
 * In the beginning the heap size is same as the array size
 */
long heapsize = SIZE;

void maxHeapify(long i){
    long largest;

    /**
     * Find right child index
     */
    long l = 2 * i + 1;

    /**
     * Compare left child against the current node
     */
    if (l < heapsize && A[l] > A[i])
        largest = l;
    else
        largest = i;

    /**
     * Find right child index
     */
    long r = 2 * i +2;

    /**
     * Compare right child against the calculated largest value node
     */
    if (r < heapsize && A[r] > A[largest])
        largest = r;

    /**
     * Swap the current value with the largest value
     */
    if (largest != i){
        /**
         * Swap the two values
         */
        std::swap(A[i], A[largest]);

        /**
         * Max heapify again rest of the heap
         */
        maxHeapify(largest);
    }
}


void buildMaxHeap(){
    register long j;
    /**
     * Start from the last parent and go to root
     */
    for (j = heapsize / 2 - 1; j >= 0; --j)
        maxHeapify(j);
}


void heapsort(){
    buildMaxHeap();
    /**
     * Start from the end of heap swap with root and decrease heap size
     * We know in max heap the biggest item is on top so swapping with the
     * last element will put the biggest value in the end. That way the
     * smallest value will be at the beginning and the biggest will be at the end
     * So by using max heap we can sort in Ascending order.
     */
    register long i;
    for (i = heapsize - 1; i > 0; --i){
        std::swap(A[0], A[i]);
        --heapsize;
        maxHeapify(0);
    }
}

int main(){
    register long i = 0;

    clock_t begin, end;
    double time_elapsed;

    srand(time(NULL));
    for (i = 0; i < SIZE; ++i)
        A[i] = rand() % SIZE;

    begin = clock();
    heapsort();
    end = clock();

    time_elapsed = (double)(end - begin) / CLOCKS_PER_SEC;

    /**
     * Comment this code if you do not want to see sorted output but just time
     */
    for(i = 0; i < SIZE; ++i)
        printf("%ld ", A[i]);

    printf("\n\nTime elapsed: %lf\n", time_elapsed);

    return 0;
}