ardalahmet.com

// ==================================================
// - File______: HeapSortInt.h ______________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef HEAP_SORT_INT_H_
#define HEAP_SORT_INT_H_

void HeapSortInt(int *pArr, int arrSize);

#endif  // HEAP_SORT_INT_H_

// ==================================================
// - File______: HeapSortInt.cpp ____________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

/* --------------------------------------------
 * --- File     : HeapSortInt.cpp           ---
 * --- Author   : Ahmet ARDAL               ---
 * --- Contact  : ardalahmet@hotmail.com    ---
 * --------------------------------------------
 */

#include "HeapSortInt.h"

// macro definitions
#define LeftChildIdx(i)     (2 * (i) + 1)
#define RightChildIdx(i)    (2 * (i) + 2)

// private function declarations
static void buildHeap(int *pArr, int arrSize);
static void heapify(int *pArr, int rootIdx, int endIdx);
static void swap(int *p1, int *p2);

// private function definitions
static void buildHeap(int *pArr, int arrSize)
{
    // startIdx is assigned the index in pArr of the last parent node
    int startIdx = (arrSize - 2) / 2;

    while (startIdx >= 0)
    {
        // sift down the node at index startIdx to the proper place such that all nodes below
        // the startIdx index are in heap order
        heapify(pArr, startIdx, (arrSize - 1));
        --startIdx;
        // after sifting down the root all nodes/elements are in heap order
    }
}

//static void heapify(int *pArr, int rootIdx, int endIdx)
//{
//    while ((rootIdx * 2 + 1) <= endIdx)   // While the root has at least one child
//    {
//        int childIdx = rootIdx * 2 + 1; // root*2+1 points to the left child
//
//        // If the child has a sibling and the child's value is less than its sibling's...
//        if (((childIdx + 1) <= endIdx) && (pArr[childIdx] < pArr[childIdx + 1]))
//        {
//            ++childIdx;    // then point to the right child instead
//        }
//
//        if (pArr[rootIdx] < pArr[childIdx]) // out of max-heap order
//        {
//            swap(&pArr[rootIdx], &pArr[childIdx]);
//            rootIdx = childIdx;   // repeat to continue sifting down the child now
//        }
//        else
//        {
//            return;
//        }
//    }
//}

static void heapify(int *pArr, int rootIdx, int endIdx)
{
    // assume left child exists and it is the maximum of childs
    int maxChildIdx = LeftChildIdx(rootIdx);
    // if left child does not exist then exit
    if (maxChildIdx > endIdx)
    {
        return;
    }

    // if right child exists and it is bigger than the left child then make it the max child
    if (((maxChildIdx + 1) <= endIdx) && (pArr[maxChildIdx + 1] > pArr[maxChildIdx]))
    {
        ++maxChildIdx;
    }

    // if root has a child bigger than itself then swap them and recurse
    if (pArr[maxChildIdx] > pArr[rootIdx])
    {
        swap(&pArr[maxChildIdx], &pArr[rootIdx]);
        heapify(pArr, maxChildIdx, endIdx);
    }
}

static void swap(int *p1, int *p2)
{
    int tmp = *p1;

    *p1 = *p2;
    *p2 = tmp;
}

// public function definitions
void HeapSortInt(int *pArr, int arrSize)
{
    int endIdx = arrSize - 1;

    // first place pArr in max-heap order
    buildHeap(pArr, arrSize);

    while (endIdx > 0)
    {
        // swap the root(maximum value) of the heap with the last element of the heap
        swap(&pArr[endIdx], &pArr[0]);

        // decrease the size of the heap by one so that the previous max value will
        // stay in its proper placement
        --endIdx;
        // put the heap back in max-heap order
        heapify(pArr, 0, endIdx);
    }
}

// ==================================================
// - File______: testHeapSortInt.cpp ________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "HeapSortInt.h"

using namespace std;

void printArr(const int *pArr, int arrSize);

int main()
{
    const int ARR_SIZE = 10;
    int arr[ARR_SIZE] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    cout << "Unsorted: ";
    printArr(arr, ARR_SIZE);
    cout << endl;

    HeapSortInt((const int *) arr, ARR_SIZE);

    cout << "Sorted: ";
    printArr(arr, ARR_SIZE);
    cout << endl;

    return 0;
}

void printArr(const int *pArr, int arrSize)
{
    for (int i = 0; i < arrSize; ++i)
    {
        cout << pArr[i] << ", ";
    }
}

// ==================================================
// - File______: HeapSortStr.h ______________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef HEAP_SORT_STR_H_
#define HEAP_SORT_STR_H_

void HeapSortStr(char **pArr, int arrSize);

#endif  // HEAP_SORT_STR_H_

// ==================================================
// - File______: HeapSortStr.cpp ____________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <cstring>
#include "HeapSortStr.h"

// macro definitions
#define LeftChildIdx(i)     (2 * (i) + 1)
#define RightChildIdx(i)    (2 * (i) + 2)

// private function declarations
static void buildHeap(char **pArr, int arrSize);
static void heapify(char **pArr, int rootIdx, int endIdx);
static void swap(char **p1, char **p2);

// private function definitions
static void buildHeap(char **pArr, int arrSize)
{
    // startIdx is assigned the index in pArr of the last parent node
    int startIdx = (arrSize - 2) / 2;

    while (startIdx >= 0)
    {
        // sift down the node at index startIdx to the proper place such that all nodes below
        // the startIdx index are in heap order
        heapify(pArr, startIdx, (arrSize - 1));
        --startIdx;
        // after sifting down the root all nodes/elements are in heap order
    }
}

//static void heapify(int *pArr, int rootIdx, int endIdx)
//{
//    while ((rootIdx * 2 + 1) <= endIdx)   // While the root has at least one child
//    {
//        int childIdx = rootIdx * 2 + 1; // root*2+1 points to the left child
//
//        // If the child has a sibling and the child's value is less than its sibling's...
//        if (((childIdx + 1) <= endIdx) && (pArr[childIdx] < pArr[childIdx + 1]))
//        {
//            ++childIdx;    // then point to the right child instead
//        }
//
//        if (pArr[rootIdx] < pArr[childIdx]) // out of max-heap order
//        {
//            swap(&pArr[rootIdx], &pArr[childIdx]);
//            rootIdx = childIdx;   // repeat to continue sifting down the child now
//        }
//        else
//        {
//            return;
//        }
//    }
//}

static void heapify(char **pArr, int rootIdx, int endIdx)
{
    // assume left child exists and it is the maximum of childs
    int maxChildIdx = LeftChildIdx(rootIdx);
    // if left child does not exist then exit
    if (maxChildIdx > endIdx)
    {
        return;
    }

    // if right child exists and it is bigger than the left child then make it the max child
    if (((maxChildIdx + 1) <= endIdx) && (strcmp(pArr[maxChildIdx + 1], pArr[maxChildIdx]) > 0))
    {
        ++maxChildIdx;
    }

    // if root has a child bigger than itself then swap them and recurse
    if (strcmp(pArr[maxChildIdx], pArr[rootIdx]) > 0)
    {
        swap(&pArr[maxChildIdx], &pArr[rootIdx]);
        heapify(pArr, maxChildIdx, endIdx);
    }
}

static void swap(char **p1, char **p2)
{
    char *tmp = *p1;

    *p1 = *p2;
    *p2 = tmp;
}

// public function definitions
void HeapSortStr(char **pArr, int arrSize)
{
    int endIdx = arrSize - 1;

    // first place pArr in max-heap order
    buildHeap(pArr, arrSize);

    while (endIdx > 0)
    {
        // swap the root(maximum value) of the heap with the last element of the heap
        swap(&pArr[endIdx], &pArr[0]);

        // decrease the size of the heap by one so that the previous max value will
        // stay in its proper placement
        --endIdx;
        // put the heap back in max-heap order
        heapify(pArr, 0, endIdx);
    }
}

// ==================================================
// - File______: testHeapSortStr.cpp ________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "HeapSortStr.h"

using namespace std;

void printArr(const char **pArr, int arrSize);

int main()
{
    const int ARR_SIZE = 10;
    char *arr[ARR_SIZE] =
    {
        "Zonguldak",
        "Rize",
        "Mardin",
        "Konya",
        "Kayseri",
        "Hatay",
        "Bursa",
        "Bitlis",
        "Antalya",
        "Ankara"
    };

    cout << "Unsorted: ";
    printArr((const char **) arr, ARR_SIZE);
    cout << endl;

    HeapSortStr(arr, ARR_SIZE);

    cout << "Sorted: ";
    printArr((const char **) arr, ARR_SIZE);
    cout << endl;

    return 0;
}

void printArr(const char **pArr, int arrSize)
{
    for (int i = 0; i < arrSize; ++i)
    {
        cout << pArr[i] << ", ";
    }
}

// ==================================================
// - File______: HeapSortGen.h ______________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef HEAP_SORT_H_
#define HEAP_SORT_H_

typedef int (*CompareFunc)(const void *, const void *);
typedef unsigned char   byte;

// generic HeapSort() function with traditional void pointers
void HeapSort(void *pArr, size_t nItems, size_t itemLen, CompareFunc compareCb);

#endif  // HEAP_SORT_H_

// ==================================================
// - File______: HeapSortGen.cpp ____________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <cstring>
#include "HeapSortGen.h"

#define LeftChildIdx(i)     (2 * (i) + 1)
#define RightChildIdx(i)    (2 * (i) + 2)

// private function declarations
static void buildHeap(void *pArr, int arrLen, size_t itemLen, void *pTempBuf, CompareFunc compareCb);
static void heapify(void *pArr, int rootIdx, int endIdx, size_t itemLen, void *pTempBuf, CompareFunc compareCb);
static void swap(void *p1, void *p2, void *pTempBuf, size_t bufLen);

// private function definitions
static void buildHeap(void *pArr, int arrLen, size_t itemLen, void *pTempBuf, CompareFunc compareCb)
{
    // startIdx is assigned the index in pArr of the last parent node
    int startIdx = (arrLen - 2) / 2;

    while (startIdx >= 0)
    {
        // sift down the node at index startIdx to the proper place such that all nodes below
        // the startIdx index are in heap order
        heapify(pArr, startIdx, (arrLen - 1), itemLen, pTempBuf, compareCb);
        --startIdx;
        // after sifting down the root all nodes/elements are in heap order
    }
}

static void heapify(void *pArr, int rootIdx, int endIdx, size_t itemLen, void *pTempBuf, CompareFunc compareCb)
{
    // assume left child exists and it is the maximum of childs
    int maxChildIdx = LeftChildIdx(rootIdx);
    // if left child does not exist then exit
    if (maxChildIdx > endIdx)
    {
        return;
    }

    // if right child exists and it is bigger than the left child then make it the max child
    if (
        ((maxChildIdx + 1) <= endIdx) &&
        (compareCb(((byte *) pArr + itemLen * (maxChildIdx + 1)), ((byte *) pArr + itemLen * maxChildIdx)) > 0)
    )
    {
        ++maxChildIdx;
    }

    // if root has a child bigger than itself then swap them and recurse
    if (compareCb(((byte *) pArr + itemLen * maxChildIdx), ((byte *) pArr + itemLen * rootIdx)) > 0)
    {
        swap(((byte *) pArr + itemLen * maxChildIdx), ((byte *) pArr + itemLen * rootIdx), pTempBuf, itemLen);
        heapify((byte *) pArr, maxChildIdx, endIdx, itemLen, pTempBuf, compareCb);
    }
}

static void swap(void *p1, void *p2, void *pTempBuf, size_t bufLen)
{
    memcpy(pTempBuf, p1, bufLen);
    memcpy(p1, p2, bufLen);
    memcpy(p2, pTempBuf, bufLen);
}

// public function definitions
void HeapSort(void *pArr, size_t arrLen, size_t itemLen, CompareFunc compareCb)
{
    int endIdx = arrLen - 1;
    byte *pTempBuf = new (std::nothrow) byte[itemLen];

    // first place pArr in max-heap order
    buildHeap(pArr, arrLen, itemLen, pTempBuf, compareCb);

    while (endIdx > 0)
    {
        // swap the root(maximum value) of the heap with the last element of the heap
        swap(((byte *) pArr + endIdx * itemLen), pArr, pTempBuf, itemLen);

        // decrease the size of the heap by one so that the previous max value will
        // stay in its proper placement
        --endIdx;
        // put the heap back in max-heap order
        heapify(pArr, 0, endIdx, itemLen, pTempBuf, compareCb);
    }

    delete [] pTempBuf;
}

// ==================================================
// - File______: testHeapSortGen.cpp ________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include <cstring>
#include "HeapSortGen.h"

using namespace std;

int cmpInts(const void *p1, const void *p2);
int cmpStrs(const void *p1, const void *p2);
void printIntArr(const int *pArr, int arrSize);
void printStrArr(const char **pArr, int arrSize);

// test code for generic HeapSort() function with traditional void pointers
int main()
{
    const int ARR_SIZE = 10;
    int arrInt[ARR_SIZE] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    cout << "Unsorted: ";
    printIntArr(arrInt, ARR_SIZE);
    cout << endl;

    HeapSort(arrInt, ARR_SIZE, sizeof(int), cmpInts);

    cout << "Sorted: ";
    printIntArr(arrInt, ARR_SIZE);
    cout << endl;

    // _____________________________________________________
    char *arrStr[ARR_SIZE] =
    {
        "Zonguldak",
        "Rize",
        "Mardin",
        "Konya",
        "Kayseri",
        "Hatay",
        "Bursa",
        "Bitlis",
        "Antalya",
        "Ankara"
    };

    cout << "Unsorted: ";
    printStrArr((const char **) arrStr, ARR_SIZE);
    cout << endl;

    HeapSort(arrStr, ARR_SIZE, sizeof(char *), cmpStrs);

    cout << "Sorted: ";
    printStrArr((const char **) arrStr, ARR_SIZE);
    cout << endl;

    return 0;
}

int cmpStrs(const void *p1, const void *p2)
{
    return strcmp(*((const char **) p1), *((const char **) p2));
}

int cmpInts(const void *p1, const void *p2)
{
    return *((const int *) p1) - *((const int *) p2);
}

void printIntArr(const int *pArr, int arrSize)
{
    for (int i = 0; i < arrSize; ++i)
    {
        cout << pArr[i] << ", ";
    }
}

void printStrArr(const char **pArr, int arrSize)
{
    for (int i = 0; i < arrSize; ++i)
    {
        cout << pArr[i] << ", ";
    }
}

// ==================================================
// - File______: Point2D.h __________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#ifndef POINT2D_H_
#define POINT2D_H_

#include <iostream>

class Point2D
{
private:
    int m_x;
    int m_y;

public:
    Point2D(int x = 0, int y = 0) : m_x(x), m_y(y)
    {
    }

    // copy constructor
    Point2D(const Point2D &pt)
    {
        m_x = pt.m_x;
        m_y = pt.m_y;
    }

    // accessor member functions
    int x() const
    {
        return m_x;
    }

    int y() const
    {
        return m_y;
    }

    void setX(int x)
    {
        m_x = x;
    }

    void setY(int y)
    {
        m_y = y;
    }

    void setXY(int x, int y)
    {
        m_x = x;
        m_y = y;
    }

    // assignment operator
    Point2D &operator =(const Point2D &pt)
    {
        m_x = pt.m_x;
        m_y = pt.m_y;

        return *this;
    }

    // less than operator
    bool operator <(const Point2D &pt) const
    {
        return (m_x < pt.m_x) && (m_y < pt.m_y);
    }

    // greater than operator
    bool operator >(const Point2D &pt) const
    {
        return (m_x > pt.m_x) && (m_y > pt.m_y);
    }

    // equality operator
    bool operator ==(const Point2D &pt) const
    {
        return (m_x == pt.m_x) && (m_y == pt.m_y);
    }

    // to print a Point2D object to stdout with an ostream object such as "cout"
    friend std::ostream &operator <<(std::ostream &out, const Point2D &pt);
};

#endif // POINT2D_H_

// ==================================================
// - File______: Point2D.cpp ________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include "Point2D.h"

std::ostream &operator <<(std::ostream &out, const Point2D &pt)
{
    return (out << "(x:" << pt.m_x << "|y:" << pt.m_y << ")");
}

// ==================================================
// - File______: HeapSortT.h ________________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

// generic HeapSort module with C++'s template mechanism

#ifndef HEAP_SORT_T_H_
#define HEAP_SORT_T_H_

// macro definitions
#define LeftChildIdx(i)     (2 * (i) + 1)
#define RightChildIdx(i)    (2 * (i) + 2)

// private function declarations
template <class T>
static void buildHeap(T *pArr, int arrSize);

template <class T>
static void heapify(T *pArr, int rootIdx, int endIdx);

template <class T>
static void swap(T *p1, T *p2);

// private function definitions
template <class T>
static void buildHeap(T *pArr, int arrSize)
{
    // startIdx is assigned the index in pArr of the last parent node
    int startIdx = (arrSize - 2) / 2;

    while (startIdx >= 0)
    {
        // sift down the node at index startIdx to the proper place such that all nodes below
        // the startIdx index are in heap order
        heapify(pArr, startIdx, (arrSize - 1));
        --startIdx;
        // after sifting down the root all nodes/elements are in heap order
    }
}

template <class T>
static void heapify(T *pArr, int rootIdx, int endIdx)
{
    // assume left child exists and it is the maximum of childs
    int maxChildIdx = LeftChildIdx(rootIdx);
    // if left child does not exist then exit
    if (maxChildIdx > endIdx)
    {
        return;
    }

    // if right child exists and it is bigger than the left child then make it the max child
    if (((maxChildIdx + 1) <= endIdx) && (pArr[maxChildIdx + 1] > pArr[maxChildIdx]))
    {
        ++maxChildIdx;
    }

    // if root has a child bigger than itself then swap them and recurse
    if (pArr[maxChildIdx] > pArr[rootIdx])
    {
        swap(&pArr[maxChildIdx], &pArr[rootIdx]);
        heapify(pArr, maxChildIdx, endIdx);
    }
}

template <class T>
static void swap(T *p1, T *p2)
{
    T tmp = *p1;

    *p1 = *p2;
    *p2 = tmp;
}

// public function definitions
template <class T>
void HeapSort(T *pArr, int arrLen)
{
    int endIdx = arrLen - 1;

    // first place pArr in max-heap order
    buildHeap(pArr, arrLen);

    while (endIdx > 0)
    {
        // swap the root(maximum value) of the heap with the last element of the heap
        swap(&pArr[endIdx], &pArr[0]);

        // decrease the size of the heap by one so that the previous max value will
        // stay in its proper placement
        --endIdx;
        // put the heap back in max-heap order
        heapify(pArr, 0, endIdx);
    }
}

#endif  // HEAP_SORT_T_H_

// ==================================================
// - File______: testHeapSortT.cpp __________________
// - Author____: Ahmet Ardal ________________________
// - Contact___: ardalahmet@hotmail.com _____________
// __________________________________________________
// - Copyright (c) 2009, Some Rights Reserved _______
// ==================================================

#include <iostream>
#include "HeapSortT.h"
#include "Point2D.h"

using namespace std;

template <class T>
void printArr(const T *pArr, int arrSize);

// test code for generic HeapSort() function with C++ templates
int main()
{
    const int ARR_SIZE = 10;
    int arrInt[ARR_SIZE] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};

    cout << "Unsorted: ";
    printArr(arrInt, ARR_SIZE);
    cout << endl;

    HeapSort(arrInt, ARR_SIZE);

    cout << "Sorted: ";
    printArr(arrInt, ARR_SIZE);
    cout << endl << endl;

    // =============================================
    Point2D arrPt[5];

    arrPt[0].setXY(9, 8);
    arrPt[1].setXY(7, 6);
    arrPt[2].setXY(5, 4);
    arrPt[3].setXY(3, 2);
    arrPt[4].setXY(1, 0);

    cout << "Unsorted: ";
    printArr(arrPt, 5);
    cout << endl;

    HeapSort(arrPt, 5);

    cout << "Sorted: ";
    printArr(arrPt, 5);
    cout << endl << endl;

    return 0;
}

template <class T>
void printArr(const T *pArr, int arrSize)
{
    for (int i = 0; i < arrSize; ++i)
    {
        cout << pArr[i] << ", ";
    }
}