cwl157

i have to make a program that lets a user add, print, delete an int value from a min heap. I am trying to do the insert first. I have heard a perferred method for inserting a number is to convert the number to binary and then the 1 tells you to insert to the right and the 0 tells you to insert to the left. How do i convert a decimal number entered by the user into binary? I have heard once the number is in binary putting the number into an array and then going through the array is the best way to see each 1 and 0 and then move through the heap accordingly? I am trying to just get the part where it tells me to move right and left correct then i will worry about actual classes and pointers and stuff. Is this the best way to do this? Does anyone have any suggestions on a different method? I am really confused at this point and really do not even know where to start. I have wrote out some simple steps in an attempt to make a plan but i do not really get how it will work.

DaWei

Your integer is a binary number as it stands, needs no conversion, if it is indeed an int. I don't know why you'd want to look at the LSB, since in C/C++ you won't lose your jockeys, efficiency wise, just testing for even (%) or comparing.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

cwl157

Ok I do not really understand what this means but here is the method i have come up with so far. As far as i know it has two problems. The first is i do not know when to end the loop right now i have it going until 32. Second, from what i have tested i need to ignore the first zeros and the first 1. I do not know how to do this. Here is what i have so far:

DaWei

If you're going to use an array as a binary tree, you need to understand how the index number relates to parent/left child/right child. Is that what you're trying to do? A min heap doesn't necessarily imply that odd (or conversely, even) numbers are to the left and the opposite are to the right.

__________________
Abstraction doesn't make it impossible to write bad code; it makes it possible to write superior code.
Contributor's Corner: Grumpy on C++ Exceptions DaWei on Pointers

hbe02

Min heap does not work that way, every node in the array has a parent and a child. for example, take an element's positon in the heap array to be "r" . its parents position is (r-1)/2. and it's left child has an inder of 2r+1. right child is 2r+2.
when you insert an element, you insert it at the end of the heap, and then you perform an operation called sifting up (not shifting!) . here you compare it to its parent heap[(r-1)/2] if it is smaller then you swap it with the parent, then you compare it to its new parent, and swap if smaller, you keep doing that until you should no longer swap, which is when the parent is smaller.

cwl157

i don't know exactly. I am trying to get the 1 and 0 and then if the number is a 0 you move to the left in the tree and if it is a 1 you move to the right in the tree and thats how you know where the next value goes for inserting and then just go back up comparing that number to the rest of the nodes swapping to meet the rules of a binary min heap. I don't know about the nodes or anything yet i was told the best thing to start with is just to enter a number and have it say the correct way to move based on the ones and zeros and after i have that i will worry about nodes and everything else.

hbe02

This is a heap implementation i did, i sent it a compare max static function class in the template, sending a min compare funciton will make it a min heap instead.

// Max-heap class
template <class Elem, class Comp> class maxheap {
private:
Elem* Heap; // Pointer to the heap array
int size; // Maximum size of the heap
int n; // Number of elements now in the heap
void siftdown(int); // Put element in its correct place
void siftup(int);
public:
maxheap(Elem* h, int num, int max) // Constructor
{ Heap = h; n = num; size = max; buildHeap(); }
int heapsize() const // Return current heap size
{ return n; }
bool isLeaf(int pos) const // TRUE if pos is a leaf
{ return (pos >= n/2) && (pos < n); }
int leftchild(int pos) const
{ return 2*pos + 1; } // Return leftchild position
int rightchild(int pos) const
{ return 2*pos + 2; } // Return rightchild position
int parent(int pos) const // Return parent position
{ return (pos-1)/2; }
bool insert(const Elem&); // Insert value into heap
bool removemax(Elem&); // Remove maximum value
bool remove(int, Elem&); // Remove from given position
void buildHeap() // Heapify contents of Heap
{ for (int i=n/2-1; i>=0; i--) siftdown(i); }
void swap(Elem *, int, int);
int find (const Elem& E) //returns position of an element..to find a duplicate with
{ // the highest propability and return its position
int pos;
for (int i = 0 ; i < n; i++)
{
if ( E.ID == Heap[i].ID )
{
pos = i ;
for (int j = i ; j < n; j++)
{
if ( E.ID == Heap[j].ID )
{
if(Heap[j].p > Heap[pos].p)
{
pos = j ;
break;
}
}
}
break;
}
}
return pos;
}
bool exist (const Elem& E) // checks if element exists in the heap.. if it doesnt after delete, then it should also be deleted from the tree
{
for (int i = 0 ; i < n; i++)
{
if( E.ID == Heap[i].ID )
{ return true ; }

}
return false ;
}
void print()
{
if (n == 0)
{
cout<<"HEAP IS EMPTY"<<endl;
}
else
{
cout<<"Heap is arranged by order of priority \n\t <ID,Priority> \n"<<endl;
for (int i = 0 ; i < n; i++)
{
cout<<Heap[i];
}
cout<<endl;
}

}
};

template <class Elem, class Comp> // Utility function
void maxheap<Elem, Comp>::siftup(int pos) {
while ((pos!=0) &&
(Comp::gt(Heap[pos], Heap[parent(pos)]))) {
swap(Heap, pos, parent(pos));
pos = parent(pos);
}
}

template <class Elem, class Comp> // Utility function
void maxheap<Elem, Comp>::siftdown(int pos) {
while (!isLeaf(pos)) { // Stop if pos is a leaf
int j = leftchild(pos); int rc = rightchild(pos);
if ((rc < n) && Comp::lt(Heap[j], Heap[rc]))
{
j = rc; // Set j to greater child's value
}
if (!Comp::lt(Heap[pos], Heap[j])) return; // Done
swap(Heap, pos, j);
pos = j; // Move down
}
}

template <class Elem, class Comp> // Insert element
bool maxheap<Elem, Comp>::insert(const Elem& val) {
if (n >= size) return false; // Heap is full
int curr = n++;
Heap[curr] = val; // Start at end of heap
siftup(curr) ;

return true;
}

template <class Elem, class Comp> // Remove max value
bool maxheap<Elem, Comp>::removemax(Elem& it) {
if (n == 0) return false; // Heap is empty
swap(Heap, 0, --n); // Swap max with last value
if (n != 0) siftdown(0); // Siftdown new root val
it = Heap[n]; // Return deleted value
return true;
}

// Remove value at specified position
template <class Elem, class Comp>
bool maxheap<Elem, Comp>::remove(int pos, Elem& it) {
if ((pos < 0) || (pos >= n)) return false; // Bad pos
swap(Heap, pos, --n); // Swap with last value
while ((pos != 0) &&
(Comp::gt(Heap[pos], Heap[parent(pos)])))
swap(Heap, pos, parent(pos)); // Push up if large key
siftdown(pos); // Push down if small key
it = Heap[n];
return true;
}

template <class Elem, class Comp>
void maxheap<Elem, Comp>::swap(Elem * heap, int x, int y) {


Elem temp = heap[x];
heap[x]=heap[y];
heap[y]=temp;


}

cwl157

mmm... yea i don't really understand a lot of that Like all the template stuff

hbe02

in your implementation , you should start at the root of the tree, compare the number to the smallest of its children using their addresses as 2r+1 and 2r+2 , if node is larger then keep going down comparing with the smallest child of the node, if the node is smaller then you have to put it in that childs position, then you have to kick the child out of that position and insert it somewhere else, so you compare with the smallest of its children and you swap appropriately, this mechanism is called sifting (not shifting!) down. you should look it up

hbe02

what do you do btw, university student..? where?