Sift down heap help

[eerieCarlise]

I'm kinda on my wit's end with this bug. My intuition tells me it has something to do with how the memory in my array goes out of wack during my swap function. It works fine during the sift up process however, only adding to my growing confusion. Any ideas as to where I went wrong? Also bonus question, what is happening in this bit of code? value += (1 << power);

#include <iostream>
#include <fstream>
#include <math.h>
using namespace std;

void readFile();
void insertHeap(int, int);
void siftUp(int);
void swap(int, int, int arr[]);
void display(int);
void siftDown(int, int);
int deleteHeap(int);

ifstream in("input.txt");
int arr[10];

int main()
{
    int heapSize = 4;
    readFile();

    display(heapSize);
    heapSize = deleteHeap(heapSize);
    display(heapSize)

    return 0;
}

void readFile()
{
    int data, i = 0;
    while (in.good())
    {
        if (in >> data)
        {
            insertHeap(data, i);
            ++i;
        }
        else
        {
            cout << "File empty...";
            exit(100);
        }
    }
}

void insertHeap(int data, int i)
{
    arr[i] = data;
    siftUp(i);
}

void siftUp(int i)
{
    if (i != 0)
    {
        int parent = (i - 1)/2;
        if (arr[parent] > arr[i])
        {
            swap(parent, i, arr);
            siftUp(parent);
        }
    }
}

void swap(int a, int b, int arr[])
{
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;

}
//not my work
void display(int heapSize)
{
    int value = 1;
    int power = 0;
    for (int i = 0; i <= heapSize; ++i)
    {
        if (i == value)
        {
            cout << endl;
            power += 1;
            //1 << power ?
            value += (1 << power);
        }
        cout << arr[i] << " ";
    }
    cout << endl << endl;
}

//always deletes first element in array, swaps w/ last element then work your way down
void siftDown(int parent, int heapSize)
{
    int min;
    int lChild = 2*parent+1;
    int rChild = 2*parent+2;
    //if theres another value other than root
    if (lChild <= heapSize)
    {
        //if there's only a left child
        if (lChild == heapSize)
            min = lChild;
        //if there's also a right child
        else
        {
            //compare left and right child
            if (arr[lChild] < arr[rChild])
               min = lChild;
            else
                min = rChild;
            //if the parent > min child, swap
            if (arr[parent] > arr[min])
            {
                swap(parent, min, arr);
                //continue until lChild becomes greater than heapSize
                siftDown(min, heapSize);
            }
        }
    }
}

int deleteHeap(int heapSize)
{
    arr[0] = arr[heapSize];
    arr[heapSize] = '\0';
    heapSize--;
    siftDown(0, heapSize);
    return heapSize;
}

[salem c]

Please read, then reformat your post.
https://www.cplusplus.com/articles/jEywvCM9/

[kyviro]

I think some formatting into code blocks would help people answer this question. Use "[|code]" and "[|/code]" (without the "|" character, of course) so that way people viewing this question can see the lines easier. Indentation would really help.

Edit: It appears somebody was quicker than I.

[eerieCarlise]

Thanks, it looks much better now

[salem c]

So what's in input.txt?

    int value = 1;
    int power = 0;
    for (int i = 0; i <= heapSize; ++i)
    {
            power += 1;
            //1 << power ?
            value += (1 << power);
    }

So 1<<power will generate successive powers of 2.
In binary, what you're generating are 1, 10, 100, 1000, 10000, 100000 etc.
Otherwise known as 1,2,4,8,16,32...
value in turn will be the sum of those, 1,3,7,15,...

[eerieCarlise]

Example of what's in txt file: 2 4 5 1 7

output:

    1
    2 5
    4 7
    
    2
    7 5
    4

[salem c]

It seems to be broken before you get to delete anything.

Why isn't 7 printed anywhere?

$ g++ -g -Wall foo.cpp
$ gdb -q ./a.out
Reading symbols from ./a.out...done.
(gdb) b 26
Breakpoint 1 at 0x400b8b: file foo.cpp, line 26.
(gdb) run
Starting program: ./a.out 
1254

1 
2 5 
4 


Breakpoint 1, main () at foo.cpp:26
26	    heapSize = deleteHeap(heapSize);
(gdb) p arr
$1 = {1, 2, 5, 4, 7, 0, 0, 0, 0, 0}
(gdb) p heapSize 
$2 = 3
(gdb) 

[eerieCarlise]

sorry, heapSize should be equal to 4, not 3 in main. I edited the post

[salem c]

> swap(parent, i, arr);
vs
> swap(arr[parent], arr[min], arr);

So why are you swapping using the contents as indices?

siftDown (parent=0, heapSize=3) at foo.cpp:96
96	    int lChild = 2*parent+1;
(gdb) 
97	    int rChild = 2*parent+2;
(gdb) 
99	    if (lChild <= heapSize)
(gdb) 
102	        if (lChild == heapSize)
(gdb) p rChild 
$3 = 2
(gdb) p lChild 
$4 = 1
(gdb) s
108	            if (arr[lChild] < arr[rChild])
(gdb) 
109	               min = lChild;
(gdb) 
113	            if (arr[parent] > arr[min])
(gdb) 
115	                swap(arr[parent], arr[min], arr);
(gdb) p min
$5 = 1
(gdb) p parent
$6 = 0
(gdb) p min
$7 = 1
(gdb) p arr[parent]
$8 = 7
(gdb) p arr[min]
$9 = 2

[eerieCarlise]

okay, I've fixed that but for some reason, it fails to enter the if (arr[parent] > arr[min) statement the second time around. Any ideas?

[MikeyBoy]

Seems like a good time to use your debugger to examine the values of arr[parent] and arr[min] . That should show you why the condition is evaluating as false.