How to implement a max heap

Question

I have the code to build a max heap, but it keeps on returning the same array I give it. I'm sure its a minor error, but I cant seem to figure it out. Any help is appreciated.

Compilable sample code:

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i; }
    int getRight(int i) { return (2 * i) + 1; }
    int getParent(int i) { return i / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int maxHeap[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[]);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int maxHeap[]) {
    int heap_size = size;
    int n = size;
    int temp;

    Build_Max_Heap(maxHeap, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        temp = maxHeap[0];
        maxHeap[0] = maxHeap[i];
        maxHeap[i] = temp;

        heap_size = heap_size - 1;
        Max_Heapify(maxHeap, 0, heap_size);
    }

    for (int i = 0; i < 8; i++) {
        std::cout << maxHeap[i] << std::endl;
    }
}

void Heaparr::Build_Max_Heap(int maxHeap[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(maxHeap, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    // int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l <= heap_size) && (heapArray[l] > heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r <= heap_size) && (heapArray[r] > heapArray[largest])) {
        largest = r;
    }

    int temp;
    if (largest != i) {
        temp = heapArray[i];
        heapArray[i] = heapArray[largest];
        heapArray[largest] = temp;

        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};
    Heaparr t;
    t.heapSort(hArray);
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
}

Answer 1

import java.util.ArrayList;
import java.util.List;

public class Heap {
    private List<Integer> heap;

    public Heap() {
        this.heap = new ArrayList<>();
    }

    public List<Integer> getGeap() {
        return new ArrayList<>(this.heap);
    }

    private int leftChild(int index) {
        return index * 2 + 1;
    }

    private int rightChild(int index) {
        return index * 2 + 2;
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private void swap(int index1, int index2) {
        int temp = heap.get(index1);
        heap.set(index1, heap.get(index2));
        heap.set(index2, temp);
    }

    public void insert(int value) {
        heap.add(value);
        int current = heap.size() - 1;

        while (current > 0 && heap.get(current) > heap.get(parent(current))) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    public static void main(String[] args) {
        int[] A = { 99, 61, 58, 18, 27, 55, 72 };
        Heap hp = new Heap();
        for (int i = 0; i < A.length; i++) {
            hp.insert(A[i]);
        }
        // PriorityQueue<Integer> q = new PriorityQueue<>();

        // System.out.println(hp.leftChild(2));
        // System.out.println(hp.rightChild(0));
        System.out.println(hp.getGeap());
    }
}

Answer 2

I made some fixed to the code (i try not to changed much the original code):

• The getLeft, getRight and getParent formulas were wrong (ex: when i == 0 children must be 1 and 2 and with your code are 0 and 1. The return type was also wrong, should be int (array index).
• Do you receive in all methods a int[] except in insert and the member variable that are double[], changed all to int[], if you need changed back all to double
• Using std::swap for swap values in the array.
• Adding the length of the array to heapSort (inside the method this info is lost, need to be passed by parameter).

Notes:

• I dont see where you use the member variable maxHeap, because all methods except getMax and insert use the array passed by parameter and not the member variable (perhaps you should initialized in the constructor or in heapSort method.
• Try to use std::vector instead of C Array

Code:

#include <iostream>
#include <cmath>

class Heaparr {
public:
    Heaparr();
    void insert(int da);
    int getLeft(int i) { return 2 * i + 1; }
    int getRight(int i) { return 2 * i + 2; }
    int getParent(int i) { return (i - 1) / 2; }
    int getMax() { return maxHeap[0]; }
    void print();
    void reheap(int num);
    void makeArray();
    void Build_Max_Heap(int heapArray[], int heap_size);
    void Max_Heapify(int heapArray[], int i, int heap_size);
    void heapSort(int heapArray[], int heap_size);

private:
    int size;
    int* maxHeap;
    int index;
    int i;
};

Heaparr::Heaparr() {
    maxHeap = nullptr;
    size = 0;
}

void Heaparr::insert(int da) {
    size++;
    int* tmp = new int[size];

    for (int i = 0; i < size - 1; i++) {
        tmp[i] = maxHeap[i];
    }

    tmp[size - 1] = da;
    delete[] maxHeap;
    maxHeap = tmp;
}

void Heaparr::heapSort(int heapArray[], int heap_size) {
    size = heap_size;
    int n = size;
    Build_Max_Heap(heapArray, heap_size);

    for (int i = n - 1; i >= 1; i--) {
        std::swap(heapArray[0], heapArray[i]);
        heap_size = heap_size - 1;
        Max_Heapify(heapArray, 0, heap_size);
    }
}

void Heaparr::Build_Max_Heap(int heapArray[], int heap_size) {
    int n = size;
    for (int i = floor((n - 1) / 2); i >= 0; i--) {
        Max_Heapify(heapArray, i, heap_size);
    }
    return;
}

void Heaparr::Max_Heapify(int heapArray[], int i, int heap_size) {
    // int n = size;
    int largest = 0;
    int l = getLeft(i);
    int r = getRight(i);

    if ((l < heap_size) && (heapArray[l] < heapArray[i])) {
        largest = l;
    } else {
        largest = i;
    }

    if ((r < heap_size) && (heapArray[r] < heapArray[largest])) {
        largest = r;
    }

    if (largest != i) {
        std::swap(heapArray[i], heapArray[largest]);
        Max_Heapify(heapArray, largest, heap_size);
    }
    return;
}

int main(int argc, char* argv[]) {
    int hArray[8] = {5, 99, 32, 4, 1, 12, 15, 8};

    Heaparr t;
    t.heapSort(hArray, sizeof(hArray)/sizeof(hArray[0]));
    for (auto v : hArray) {
        std::cout << v << ", ";
    }
    std::cout << std::endl;
    return 0;
}

Output: 99, 32, 15, 12, 8, 5, 4, 1,

Tested in GCC 4.9.0 with C++11

Answer 3

If you're willing to consider alternative implementations, then here is one:

#define MIN_TYPE  0
#define MAX_TYPE ~0

template<int TYPE,typename ITEM>
class Heap
{
public:
    Heap(int iMaxNumOfItems);
    virtual ~Heap();
public:
    bool AddItem(ITEM*  pItem);
    bool GetBest(ITEM** pItem);
protected:
    int  BestOfTwo(int i,int j);
    void SwapItems(int i,int j);
protected:
    ITEM** m_aItems;
    int    m_iMaxNumOfItems;
    int    m_iCurrNumOfItems;
};

template<int TYPE,typename ITEM>
Heap<TYPE,ITEM>::Heap(int iMaxNumOfItems)
{
    m_iCurrNumOfItems = 0;
    m_iMaxNumOfItems = iMaxNumOfItems;
    m_aItems = new ITEM*[m_iMaxNumOfItems];
    if (!m_aItems)
        throw "Insufficient Memory";
}

template<int TYPE,typename ITEM>
Heap<TYPE,ITEM>::~Heap()
{
    delete[] m_aItems;
}

template<int TYPE,typename ITEM>
bool Heap<TYPE,ITEM>::AddItem(ITEM* pItem)
{
    if (m_iCurrNumOfItems == m_iMaxNumOfItems)
        return false;

    m_aItems[m_iCurrNumOfItems] = pItem;

    for (int i=m_iCurrNumOfItems,j=(i+1)/2-1; j>=0; i=j,j=(i+1)/2-1)
    {
        if (BestOfTwo(i,j) == i)
            SwapItems(i,j);
        else
            break;
    }

    m_iCurrNumOfItems++;

    return true;
}

template<int TYPE,typename ITEM>
bool Heap<TYPE,ITEM>::GetBest(ITEM** pItem)
{
    if (m_iCurrNumOfItems == 0)
        return false;

    m_iCurrNumOfItems--;

    *pItem = m_aItems[0];
    m_aItems[0] = m_aItems[m_iCurrNumOfItems];

    for (int i=0,j=(i+1)*2-1; j<m_iCurrNumOfItems; i=j,j=(i+1)*2-1)
    {
        if (j+1 < m_iCurrNumOfItems)
            j = BestOfTwo(j,j+1);
        if (BestOfTwo(i,j) == j)
            SwapItems(i,j);
        else
            break;
    }

    return true;
}

template<int TYPE,typename ITEM>
int Heap<TYPE,ITEM>::BestOfTwo(int i,int j)
{
    switch (TYPE)
    {
        case MIN_TYPE: return *m_aItems[i]<*m_aItems[j]? i:j;
        case MAX_TYPE: return *m_aItems[i]>*m_aItems[j]? i:j;
    }
    throw "Illegal Type";
}

template<int TYPE,typename ITEM>
void Heap<TYPE,ITEM>::SwapItems(int i,int j)
{
    ITEM* pItem = m_aItems[i];
    m_aItems[i] = m_aItems[j];
    m_aItems[j] = pItem;
}

And here is a usage example:

typedef int ITEM;
#define SIZE 1000
#define RANGE 100

void test()
{
    ITEM* pItem;
    ITEM aArray[SIZE];
    Heap<MIN_TYPE,ITEM> cHeap(SIZE);

    srand((unsigned int)time(NULL));

    for (int i=0; i<SIZE; i++)
    {
        aArray[i] = rand()%RANGE;
        cHeap.AddItem(aArray+i);
    }

    for (int i=0; i<SIZE; i++)
    {
        cHeap.GetBest(&pItem);
        printf("%d\n",*pItem);
    }
}

Description:

• This class stores up to N items of type T

• It allows adding an item or extracting the best item

• Supported operations are accomplished at O(log(n)), where n is the current number of items

Remarks:

• T is determined at declaration and N is determined at initialization

• The meaning of "best", either minimal or maximal, is determined at declaration

• In order to support Heap<MIN,T> and Heap<MAX,T>, one of the following options must be viable:

  1. bool operator<(T,T) and bool operator>(T,T)

  2. bool T::operator<(T) and bool T::operator>(T)

  3. T::operator P(), where P is a type, for which, one of the above options is viable