Implementacja kopca i kolejki prio.

Witam, mam problem ponieważ muszę napisać ten program na laborki, a w literaturze heap z kolejką są zawsze w jednej klasie (poloączone). Nie mam pojęcia jak to zrobić proszę o pomoc... Poniżej treść zadania:

1.implementacja kopca ekstrachującego największy element oparty na interfejsie:

public interface maxHeap
{
    public void clear();//oproznia stos
    public Object extractMin();//usuwa największy
    public Object getMax();//pobiera największy bez usuwania
    public int getSize();//liczba el. kopca
    public void insert(Object obj);//dodaje do kopca
    public boolean isEmpty();//czy kopiec pusty
    public void makeHeap(Object[] arr);//buduje kopiec na podstawie tablicy
}

2.Zaimplementuj kolejke prior. wykorzystującą kopiec, interfejs:

public interface prioQueue
{
    public boolean add(Object obj);//dodaje do kolejki
    public void clear();//usuwa all z kolejki
    public boolean offer(Object obj);//wstawia element do kolejki
    public Object peek();//pobiera pierwsszy obj z kolejki nie usuwając go
    public Object poll();//jak wyżej tylko z usuwaniem ;)
    public boolean remove(Object obj);//jeśli objekt istnieje - usuń go z kolejki
    public int size();//rozmiar kol.<code>
}

Użyj delegacji. Najpierw stwórz klasę MaxHeapImplementation. Niech ta klasa reprezentuje kopiec. Niech implementuje interfejs maxHeap.

Następnie stwórz klasę PrioQueueImplementation, reprezentującą kolejkę priorytetową. Niech ta klasa implementuje interfejs prioQueue. Zacznij od napisania pustych ciał tych wszystkich metod, których wymaga interfejs prioQueue. Dodaj do klasy pole prywatne typu maxHeap. Nazwij to pole heap i podstaw do niego instancję wcześniej utworzonej klasy MaxHeapImplementation.

Następnie możesz użyć delegacji. Niech metody klasy PrioQueueImplementation wywołują metody obiektu heap, o tak:

class PrioQueueImplementation implements prioQueue {
  maxHeap heap = new MaxHeapImplementation();

  ...

  public void clear() {
    heap.clear();
  }

  public int size() {
    return heap.size();
  }

  public int offer(object addedObject) {
    heap.insert(addedObject);
  }

  ... i tak dalej...
}

Musisz po prostu wykorzystać metody obiektu heap w metodach Twojej kolejki priorytetowej. Powinno to być proste, bo kopiec doskonale sprawdza się w roli kolejki. Większość, jeśli nie wszystkie metody będą jedynie przekazywały żądania do obiektu heap.

Aha, radzę Ci zmienić nazwy tych interfejsów tak, by zaczynały się wielką literą. Tak to się w Javie przyjęło. I, na Boga, zmień nazwę maxHeap.extractMin na extractMax, skoro metoda ma usunąć NAJWIĘKSZY element!

Dzięki wielkie, nie wiedziałem, że po prostu jedna z tych klas będzie wywoływała drugą i w zasadzie całe kodowanie ograniczy się do klasy kopca ;). Oczywiście interfejsy napisałem z dużych liter, tutaj tak mi się jakoś napisało... Cały problem tkwi w tym czym się różni w zasadzie kolejka priorytetowa od max kopca... No i czy w kopcu powinienem zastosować metody prywatne sink i swim? Aha - jak porozmieszczane są elementy w tablicy w kopcu? Jakoś uporządkowanie (rosnąco naprzyklad) czy wedlug tych wzorkow określających położenie synów i rodzicow (rodzic - x, to synowie: 2x i 2x+1)? Proszę o odpowiedzi :D Dzięki z góry

//Kolejka FiFo

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <iostream>
#include <string>
#include <iomanip>
using namespace std;

struct TElem
{
TElem *next;
char label[4];
};

TElem *head = 0;

int Pusta()
{
return head == 0;
}

TElem *last()
{
TElem *e = head;
if( e )
for( ; e->next; e = e->next);
return e;
}

TElem *find(char *s)
{
TElem *e = head;
for( ; e && stricmp(e->label, s) != 0; e = e->next);
return e;
}

int getCount()
{
int n;
TElem *e = head;
for(n = 0; e; e = e->next)
n++;
return n;
}

void list()
{
TElem *e = head;
for(int n = 0 ; e; e = e->next)
printf("%3d %s\n", ++n, e->label);
}

int add()
{
char s[256];
puts("Wpisz identyfikator: ");
gets(s);

if( !s[0] ) 
return 0; 

if( find(s) )  
{
    printf("ten już stoi w kolejce...\n");
    return 0;
}

TElem *e = (TElem*)malloc(sizeof(*e) - sizeof(e->label) + strlen(s)+1);
if( !e ) 
{ 
    puts("Brak pamięci!\n"); return -1; 
}

e->next = 0;
strcpy(e->label, s);

TElem *lst = last();
if( lst ) 
    lst->next = e; 
if( !head ) 
    head = e;  

return 1;
}

int del()
{
if( !head ) return 0;

TElem *e = head;
head = e->next;     

printf("%s - wychodzi\n", e->label);
free(e); 
return 1;

}

void manipuluj()
{
char s[80]; s[0] = '1';
while( s[0] )
{
if( s[0] >= '1' && s[0] <= '3' )
printf("1: Dodaj 2: Usun 3: Lista Enter: Wyjscie\n>");

    gets(s);
    switch( *s )
    {
        case '1': 
             add(); 
             break;
        case '2': 
             del(); 
             break;
        case '3': 
             list(); 
             break;
        case 27 : 
             s[0] = 0; 
             break;
    }
}

}

int main()
{
manipuluj();
return 0;
}

// Co to jest STL?
jak zrobic do tego zamiane

W API java masz już zaiplementowaną kolejkę priorytetową: http://download.oracle.com/javase/6/docs/api/java/util/PriorityQueue.html
Możesz sobie podglądnąć źródła i zobaczyć jak została zaimlementowana.
A przykład implementacji kopca masz tu: http://www.java-tips.org/java-se-tips/java.lang/priority-queue-binary-heap-implementation-in-3.html