Problem mit Binary Heap

[Cpp_Junky]

Hi Leute!

Ich hab mal etwas mit einem "Binary Heap" rumgespielt. Das Problem ist, das auf (Array) Position [0] nicht immer der kleinste Wert steht (Wie es aber eigentlich sein sollte). Woran liegt das ? Müssen in einem "BinHeap" alle eingefügten Elemente verschieden sein ? (Dürfen die selben Werte mehrmals vorkommen ?)

Hier ist der Source zum Einfügen, Sortieren und Auslesen des Heap:

#define PARENT(i) ((i-1)/2)
#define LEFT(i)   (2*(i)+1)
#define RIGHT(i)  (2*(i)+2)

type heap[MAXN];
int heapsize=0;

void heapify (int i) // Ein Element auf die Richtige Position bringen (quasi sortieren)
{
  int l,r,smallest;
  type tmp;

  l = LEFT(i);
  r = RIGHT(i);
  smallest = l<heapsize && less(heap[l],heap[i]) ? l : i;
  if (r<heapsize && less(heap[r],heap[smallest])) smallest = r;
  if (smallest!=i)
    {
      tmp=heap[i]; heap[i]=heap[smallest]; heap[smallest]=tmp;
      heapify(smallest);
    }
}

void insert (type x) // Ein Element einfügen
{
  int i = heapsize++;
  while (i>0 && less(x,heap[PARENT(i)]))
    {
      heap[i] = heap[PARENT(i)];
      i = PARENT(i);
    }
  heap[i] = x;
}

type minimum() // Kleinstes Element holen
{ 
   return heap[0]; 
}

type extract_min() // Kleinstes Element zurückgeben und dann rausschmeissen
{
  type min;

  assert(heapsize>=1);  
  min = heap[0];
  heap[0] = heap[--heapsize];
  heapify(0);
  return min;
}