Solved

Heap help!

Posted on 1998-05-13
8
366 Views
Last Modified: 2012-06-27
I have a working array class that I am trying to base a (Binary tree) heap class on. I would like to know the code for (or at least get some direction on) the following code for the heap class: the copy constructor, the upheap, and the downheap. I have everything else I need. Let me mention that although this is for homework, it is more for self study.

Thank you very much.
0
Comment
Question by:jdixon
  • 4
  • 3
8 Comments
 
LVL 22

Expert Comment

by:nietod
ID: 1176915
I'm not familar with this terminology.  By binary tree heap class, do you mean a class for implementing a heap that uses a binary tree?  Or do you mean a binary tree class that uses the heap to store the nodes?
0
 

Author Comment

by:jdixon
ID: 1176916
I apologize.

What I mean is a class for implementing a heap using a binary tree. The binary tree is represented using a dynamic array. If you like, I can give you the code for the array class.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176917
I'm afraid I'm more curious than helpful in this area.  It seems strange to me that you want to impliment a heap as a class.  I can't image what the advantage would be.  For example, you want code for a copy constructor.  What should the copy constructor do?  It shouldn't copy the data in the heap, there would be no points to the data so it would never get freed.  I gues the copy constructor could create a new heap of the same size as the source heap, but with no objects allocated in it?  Is that what you were planning?
0
Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

 

Author Comment

by:jdixon
ID: 1176918
Sorry Nietod, I guess this query is more dicey than I thought.

I think my instructor wanted to use this excerise to show us how dynamic arrays and trees can be related.

The only thing that I can think of for the copy constructor is that it will allocate memory for a heap that will be the same size as the source heap. After the memory has been allocated the data would be copied into the newly allocated array, probably with a small loop. The destructor (I guess) would release that dynamic memory.

Like I said, I can give you the .h and .cpp files that I have, but if this is getting too sticky I would understand because believe me I¹m more confused than you are.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1176919
The copy constructor could copy the data from the source heap.  But what would be the point?  The data in the source heap is being "used" in the sense that whatever created the data (requested it from the heap) has pointers to the data and can use the data.  but if you create a copy of the data, no one has pointers to the copies so no one can use the data.  Its kinda like

char *StrPtr1 = new char[100]; // this is useful.
new char[100]; // This is useless.  I can't access the data created!

Are you sure you want a copy constructor?  My intuition would be that the class should declare a private copy constructor and not implement it.  This technique prevents the class from being copied.  This makes sense to me.  It yould allow you to declare the heap class objects, but could not pass them by value.

I'd be happy to look at the code, but I'm going away today.  I'll be back next tuesday.  hopefully you'll get more help before then.
0
 

Author Comment

by:jdixon
ID: 1176920
Okay, thanks alot nietod.
0
 
LVL 4

Accepted Solution

by:
sganta earned 100 total points
ID: 1176921
Hai jdixon !

I am having  2 solutions for creating HEAP with different definitions.

I SOLUTION :
------------
HEAP : A heap is a complete binary tree with the property that the value at each node is at least
       as large as its children (if they exist).

#include <iostream.h>

const int MAX = 80;

/* If you want you can include this in Class object also */

void heap(int heap_array[],int n);

void main(void)
{
   int arr[MAX],i,j,n;
   
   /* First you store all the elements in the ARRAY
      whatever order it is */

   cout << "Enter the no. of elements in the array : ";
   cin >> n;
 
   for (i=0;i<n;i++)
   {
      cout<<"Enter the element "<<i<<" : ";
      cin >> arr[i];
   }

   /* Assuming that 1st element in the array is heaped
      and from 2 element onwards this will place in a proper position */

   if (n > 0) // If there is more than one record then only heap is required
      for (i=1; i<n; i++)
          heap(arr,i);
}


void heap(heap_array[],n)  /* Heap Creation by inserting one item at a time
                              Inserts the value in heap_array[n] into the heap which
                              is stored at heap_array[1] to heap_array[n-1] */
{  
   int i,j,k;
   j = n;
   i = n/2;
   item = heap_array[n];
   
   while (i>=0 && heap_array[i] < item)
   {
      heap_array[j] = heap_array[i];  /* Move the parent down */
      j = i;
      i /= 2;                        /* Parent of heap i is at i/2 */
   }

   heap_array[j] = item;     /* A place for heap_array[n] is found */
}
     

II SOLUTION
 
   This is another algorithm for creating a heap which has the nice property that its worst
   case time is an order of magnitude faster than n-1 calls of above program.

#include <iostream.h>

const int MAX = 80;

/* If you want you can include this in Class object also */

void adjust(int heap_array[],int i,int n);
void heapify(int heap_array[],int n);

void main(void)
{
   int arr[MAX],i,j,n;
   
   /* First you store all the elements in the ARRAY
      whatever order it is */

   cout << "Enter the no. of elements in the array : ";
   cin >> n;
 
   for (i=0;i<n;i++)
   {
      cout<<"Enter the element "<<i<<" : ";
      cin >> arr[i];
   }
   
   heapify(arr,n);
}

void heapify(int heap_array[],int n)
{
   /* Readjust the elements in heap_array(0:n-1) to form a heap */
   int i,j;
   j = n/2;

   for (i=j;i>=0;i--)
     adjust(heap_array,i,n);
}

void adjust(int heap_array[],int i, int n)
{
  /* The complete binary trees with roots heap(2*i) and heap(2*i+1) are
     combined with heap(i) to form a single heap, 0<= i < n
     No node has an address >= n or less than 0 */

  int j,item,k;
 
  j = 2*i;
  item = heap_array[i];

  while ( j < n)
  {
    if ( j<(n-1) && heap_array[j] < heap_array[j+1] ) /* Compare left and right childs */
       j++;
 
    if (item >= heap_array[j])
       return; /* item has been already in heap order */
    else
    {
       k = j/2;
       heap_array[k] = item;
    }
  }

  k = j/2;
  heap_array[k] = item;
  return;
}

I hope these solutions are more than sufficient. If you have any problem, you are
welcome to contact me either EE or through my E-Mail sganta@ch.oracle.com

JESUS LOVES YOU - sganta
0
 

Author Comment

by:jdixon
ID: 1176922
Yes, yes, yes. You hit it on the head. Thanks a lot.
0

Featured Post

Announcing the Most Valuable Experts of 2016

MVEs are more concerned with the satisfaction of those they help than with the considerable points they can earn. They are the types of people you feel privileged to call colleagues. Join us in honoring this amazing group of Experts.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Title # Comments Views Activity
Find Visual Studio Tools 2 113
Socket Programming (Unix) 8 142
Error C2678: binary '!=': no operator found... 4 61
gdb doesn't stop on breakpoint 2 97
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

820 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question