4
\$\begingroup\$

The code reads in integer array from user input and builds a minimum heap via an iterative scheme. Are there any edge cases in which this approach would fail?

For the following test case/command sequence:

1 4 3 10 12 6 -1
remove
remove
print

My output is 4 6 10 12 instead of 4 10 6 12, is this an invalid implementation?

#include <iostream>
#include <string>
#include <sstream>
#include <stdexcept>
#include <cmath>

int readheap(int* theheap) {
    std::string num;
    int val = 0;
    int size = 0;
    std::cout << "Enter the elements of heap" << std::endl;
    std::getline(std::cin, num);
    std::istringstream iss(num);    
    while (iss >> val) {
        if (val != ' ' && val > 0){
            theheap[size] = val;
            ++size;
        }
    }
    if(size <= 1) {
        throw std::runtime_error("Invalid user input");
    }

for (int k = 1; k < size; ++k) {

        if (theheap[k] > theheap[(k - 1) / 2])  { 
            int j = k; 

            while (theheap[j] > theheap[(j - 1) / 2])  { 
                std::swap(theheap[j], theheap[(j - 1) / 2]); 
                j = (j - 1) / 2; 
            }
        }
    }
    for (int k = size - 1; k > 0; --k) {
        std::swap(theheap[0], theheap[k]);           

        int j = 0, index; 

        do { 
            index = (2 * j + 1);  

            if (theheap[index] < theheap[index + 1] && index < (k - 1)) 
                ++index; 

            if (theheap[j] < theheap[index] && index < k) 
                std::swap(theheap[j], theheap[index]); 

            j = index; 

        } while (index < k); 
    } 
    std::cout << "Size of heap is " << size << '\n';
    return size;
}

void heapRemove(int* theheap, int& size) {
    for(int i=0; i<size-1; ++i){
        theheap[i] = theheap[i+1];
    }
    int* x = theheap;
    x = nullptr;
    delete x;
    size--; 
    for (int k = 1; k < size; ++k) {

        if (theheap[k] > theheap[(k - 1) / 2])  { 
            int j = k; 

            while (theheap[j] > theheap[(j - 1) / 2])  { 
                std::swap(theheap[j], theheap[(j - 1) / 2]); 
                j = (j - 1) / 2; 
            }
        }
    }
    for (int k = size - 1; k > 0; --k) {  
        std::swap(theheap[0], theheap[k]);      

        int j = 0, index; 

        do { 
            index = (2 * j + 1);  

            if (theheap[index] < theheap[index + 1] && index < (k - 1)) 
                ++index; 

            if (theheap[j] < theheap[index] && index < k) 
                std::swap(theheap[j], theheap[index]); 

            j = index; 

        } while (index < k); 
    }
}

void heapPrint(int* theheap, int size) {
    for (int i = 0; i < size; ++i){
        std::cout << theheap[i] << ' ';
    }
    std::cout << '\n';
}

int main() {
    int* theheap = new int[10];
    int size = readheap(theheap);
    heapPrint(theheap, size);
    heapRemove(theheap, size);
    heapPrint(theheap, size);
    std::cout << size << std::endl;
    return 0;
}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ There is this post about converting recursive code to iterative. stackoverflow.com/questions/159590/…. You can convert a known algorithm. \$\endgroup\$
    – shanif
    Apr 10, 2020 at 8:43
  • \$\begingroup\$ Is a 1-element heap really invalid user input? (well, you asked for edge cases...) \$\endgroup\$ Apr 10, 2020 at 12:08
  • \$\begingroup\$ I reversed the change you made to the code in revision (i.e. if(size < 1) ). Please do not update the code in your question. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ Jun 11, 2020 at 22:52
  • \$\begingroup\$ @mypronounismonicareinstate, yes that should be if(size < 1). \$\endgroup\$ Jun 11, 2020 at 22:54

3 Answers 3

2
\$\begingroup\$

Memory over-runs

readheap is non-size-aware, so it's wide open to an overrun error (or even a deliberate overrun attack). Pass in a size, or use a sized data structure like a vector.

Indentation

You should fix it up for this line:

for (int k = 1; k < size; ++k) {

Order-of-operations

Neither of these expressions need parentheses:

index = (2 * j + 1);  

index < (k - 1)

Deleting a null?

x = nullptr;
delete x;

Does that actually run without crashing?

Const arguments

void heapPrint(int* theheap, int size) {

should be

void heapPrint(const int *theheap, int size) {
\$\endgroup\$
1
  • \$\begingroup\$ The specific problem I'm solving requires the specific function signatures I utilized. No vectors, just pointers to integers. \$\endgroup\$ Jun 11, 2020 at 23:00
2
\$\begingroup\$
  1. Explicit use of new and delete for memory management is old school and very very prone to memory leaks. Use containers like std::vector or std::array. In current code, you are leaking memory pointed by theheap pointer.
  2. Function readheap is doing two things. Reading input from cin into array theheap and then converting theheap array into actual heap. Split it into separate functions. ReadInput and Heapify
  3. To improve code readability, index operation like theheap[(j - 1) / 2] or index = (2 * j + 1) can be encapsulated in GetParent, GetLeftChild, GetRightChild like APIs.
  4. Heapify in iterative mode can look like below. Please note switching from recursion from iteration shouldn't change code logic. Recursion vs iteration can be seen as embedding difference.
    void BuildHeap(std::vector<int>& theHeap)
    {
        for (int i = theHeap.size() / 2; i >= 0; i--)
        {
            Heapify(theHeap, i);
        }
    }

    void Heapify(std::vector<int>& theHeap, size_t index)
    {
       // Next three lines (stack and while loop) needed for converting recursion to iteration. If you remove these three lines and add recusrion call in place of callStack.push leaving other code unchanged, you will get recursive version of Heapify. 
        std::stack<int> callStack;
        callStack.push(index);
        while (!callStack.empty())
        {
            callStack.pop();
            size_t left = GetLeft(index);
            size_t right = GetRight(index);
            size_t smallest = index;
            if (left < theHeap.size() && theHeap[left] < theHeap[smallest])
                smallest = left;
            if (right < theHeap.size() && theHeap[right] < theHeap[smallest])
                smallest = right;

            if (smallest != index)
            {
                auto temp = m_buffer[index];
                m_buffer[index] = m_buffer[smallest];
                m_buffer[smallest] = temp;
                callStack.push(smallest); // Line needed for converting recursion to iteration
            }
        }
    }
\$\endgroup\$
3
  • 1
    \$\begingroup\$ The std::floor is unnecessary for integer division. \$\endgroup\$
    – L. F.
    Apr 13, 2020 at 10:00
  • \$\begingroup\$ @L.F. Yes...my bad..correcting it \$\endgroup\$
    – nkvns
    Apr 13, 2020 at 10:17
  • \$\begingroup\$ The specific problem I'm solving requires the function signatures I utilized. No vectors, just pointers to integers. \$\endgroup\$ Jun 11, 2020 at 22:47
1
\$\begingroup\$

The heapRemove algorithm

heapRemove appears to remove the root element from the heap. However, it implements some sort of combination of "bubble up" (applied to every element) and "bubble down" (also applied to every element). That's extreme overkill, and turns what should be an O(log n) operation into an O(n log n) operation - that's not good.

Maybe the reason your code works that way, is that your solution for removing the root element was shifting every element down by one position. Don't do that, it already costs O(n) time just to do that, and it breaks the heap property to an unncessary degree so it takes a lot of work to restore the heap. The usual (and fast) solution is taking the last element of the heap and drop it into theHeap[0], then bubble down from the root until the heap property is restored.

readheap

readheap mixes IO and algorithms, when possible I recommend separating them, and it is possible here. readheap also mixes tons of bubble up and bubble down, which is again overkill. Pick one strategy and use it, not both. Applying bubble up to each element results in an O(n log n) heap construction algorithm, applying bubble down in a particular way can give you an O(n) heap construction algorithm.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.