δυαδικός σωρός (heap)

[Joholos]

Ξερετε που μπορω να βρω πληροφοριες σχετικα με το πως να υλοποιησω προγραμμα με εναν δυαδικο σωρο που θα αποθηκεύει την πληροφορία εσωτερικά σε πίνακα και θα υποστηρίζει καποιες πραξεις..Θελω πληροφοριες για γλωσσες java ή C++ γιατι με C φανταζομαι θα ειναι περιπλοκο επειδη θα θελει pointers..

[Vlaaad]

http://www.java-tips.org/java-se-tips/java.lang/priority-queue-binary-heap-implementation-in-3.html

 

Εδω φιλε μου.Νομιζω οτι ειναι αυτο που ζητας

[Joholos]

σε ευχαριστω πλ vlaaad!

 

εχω κανει σε C++ εναν κωδικα οπου να κανει add print και delete ενς αριθμου σε ενα heap.θελω να φτιαξω και μια πραξη Ηeap(int max_size) οπου να επιστρέφει έναν κενό σωρό με μέγιστο δυνατό μέγεθος max_size, null αν δεν υπάρχει διαθέσιος χώρος

 

class heapNode

{

private:

int value;

 

public:

heapNode *left;

heapNode *right;

 

//constructor

heapNode(int newValue)

{

value = newValue;

left = NULL;

right = NULL;

}

 

//get value

int getValue()

{

return value;

}

 

//get right

heapNode* getRight()

{

return right;

}

 

//get left

heapNode* getLeft()

{

return left;

}

 

//set value

void setValue(int newValue)

{

value = newValue;

}

 

// set right

void setRight(heapNode *newRight)

{

right = newRight;

}

 

// set left

void setLeft(heapNode *newLeft)

{

left = newLeft;

}

 

}; // end of heapNode class

 

//insert print and delete methods for the min heap

class heap

{

private:

heapNode *root;

int counter;

 

public:

//constructor

heap()

{

counter = 0;

root = NULL;

}

 

void realInsert(int ar[], int pos, heapNode *parent, heapNode *newNode)

{

if(ar[pos] == 0)

{

if (parent->getLeft() == NULL)

parent->setLeft(newNode);

else

realInsert(ar, pos-1, parent->left, newNode);

if(parent->getLeft()->getValue() < parent->getValue())

{

int tempParentLeft = parent->getLeft()->getValue();

int tempParent = parent->getValue();

parent->setValue(tempParentLeft);

parent->left->setValue(tempParent);

}

}

else if(ar[pos] == 1)

{

if (parent->getRight() == NULL)

parent->setRight(newNode);

else

realInsert(ar, pos-1, parent->right, newNode);

if(parent->getRight()->getValue() < parent->getValue())

{

int tempParentRight = parent->getRight()->getValue();

int tempParent = parent->getValue();

parent->setValue(tempParentRight);

parent->right->setValue(tempParent);

}

}

}

 

// find the spot to put new value

void insertSpot(int option)

{

heapNode *newNode = new heapNode(option);

counter++;

if(root == NULL)

{

root = newNode;

}

 

else

{

int arrayValue;

bool isOne = false;

int ar[32];

int i;

int temp = counter;

for(i = 0; i < 32; i++)

{

arrayValue = temp % 2;

temp = temp / 2;

ar = arrayValue;

}

 

for(i = 0; i < 32; i++)

cout << ar << " ";

cout << endl;

 

i=31;

while(i >= 0)

{

if(ar == 1)

isOne = true;

if(isOne == true)

break;

i--;

}

i--;

cout << "Broke loop with i = " << i << endl;

realInsert(ar, i, root, newNode);

}

}

 

//call printNode

void print()

{

cout << "Printing the heap...\n";

printNode(root, 0);

}

 

//print tree with spaces for levels of the tree

void printNode(heapNode *node, int level)

{

if(node != NULL)

{

printNode(node->getLeft(), level + 1);

for(int i = 0; i < level; i++)

cout << "\t";

cout << node->getValue();

cout << "\n";

printNode(node->getRight(), level + 1);

}

}

 

// get root

heapNode* getRoot()

{

return root;

}

 

int realDelete(int ar[], int pos, heapNode *parent)

{

heapNode *tempNode;

if(parent->getLeft() == NULL)

{

if (ar[pos] == 0)

{

tempNode = parent;

parent = NULL;

}

else

realDelete(ar, pos-1, parent->left);

}

else if(parent->getRight() == NULL)

{

if (ar[pos] == 1)

{

tempNode = parent;

parent = NULL;

}

else

realDelete(ar, pos-1, parent->right);

}

return tempNode->getValue();

}

 

 

/*//perculate down to reorganize tree

void purculateDown(heapNode *parent)

{

if(parent->getValue() > parent->left->getValue())

{

int tempParentLeft = parent->getLeft()->getValue();

int tempParent = parent->getValue();

parent->setValue(tempParentLeft);

parent->left->setValue(tempParent);

}

else if(parent->getValue() > parent->right->getValue())

{

int tempParentRight = parent->getRight()->getValue();

int tempParent = parent->getValue();

parent->setValue(tempParentRight);

parent->right->setValue(tempParent);

}

}*/

 

//delete the root

/*int realDelete(int ar[], int pos, heapNode *parent)

{

heapNode *tempNode = NULL;

if(pos == 0)

{

if (ar[pos] == 0)

{

tempNode = parent;

parent = NULL;

}

if(ar[pos} != 0)

realDelete(ar, pos-1, parent->left);

 

if(ar[pos] == 1)

{

tempNode = parent;

parent = NULL;

}

if(ar[pos] != 1)

realDelete(ar, pos-1, parent->right);

}

 

return tempNode->getValue();

}*/

 

// find the the last spot for deletion

void deleteSpot()

{

 

if (root == NULL)

cout << "Error. The tree is empty.\n";

else if(counter == 1)

{

root = NULL;

}

else

{

int arrayValue;

bool isOne = false;

int ar[32];

int i;

int temp = counter;

for(i = 0; i < 32; i++)

{

arrayValue = temp % 2;

temp = temp / 2;

ar = arrayValue;

}

 

for(i = 0; i < 32; i++)

cout << ar << " ";

cout << endl;

 

i=31;

while(i >= 0)

{

if(ar == 1)

isOne = true;

if(isOne == true)

break;

i--;

}

i--;

cout << "Broke loop with i = " << i << endl;

realDelete(ar, i, root);

root->setValue(realDelete(ar, i, root));

cout << "Deleted Value = " << root->getValue() << endl;

//purculateDown(root);

counter--;

 

}

}

 

}; // end of heap class

 

// menu with add, print, delete choices call methods from heap class

int main()

{

int option;

int value;

heap *myHeap;

myHeap = new heap();

 

 

while(option != 4)

{

cout << "1. Add a value. \n"

<< "2. Print the heap. \n"

<< "3. Delete the root. \n"

<< "4. Quit. \n"

<< "Please make a selection: ";

cin >> option;

 

if(option == 1)

{

cout << "Please enter a value: ";

cin >> value;

myHeap->insertSpot(value);

}

 

if(option == 2)

myHeap->print();

 

if(option == 3)

myHeap->deleteSpot();

}

return 0;

}

[Redman1990]

Τι μου θυμιζει αυτο τι μου θυμιζει!! Α ναι project στις Δομες.

Για αλλη μια φορα project του ceid στο insomnia. Το google σε προδωσε. Ελπιζω για το δικο σου καλο να μη αντιγραψουν πολλοι τον παραπανο κωδικα.