Chapter 9 Heap Structures

9.1 Min-Max Heaps

Program 9.1 : Procedure to insert into a min-max heap

void min_max_insert(element heap[], int *n, element item){
/* insert item into the min-max heap */
   int parent;
   (*n)++;
   if(*n == MAX_SIZE){
      fprintf(stderr, "The heap is full\n");
      exit(1);
   }
   parent = (*n) / 2;
   if(!parent)
   /* heap is empty, insert item into first position */
      heap[1] = item;
   else switch(level(parent)){
      case FALSE: /* min level */
         if(item.key < heap[parent].key){
            heap[*n] = heap[parent];
            verify_min(heap, parent, item);
         }
         else
            verify_max(heap, *n, item);
         break;
      case TRUE: /* max level */
         if(item.key > heap[parent].key){
            heap[*n] = heap[parent];
            verify_max(heap, parent, item);
         }
         else
            verify_min(heap, *n, item);
   }
}

Program 9.2 : verify_max：function

void verify_max(element heap[], int i, element item){
   /* follow the nodes form the max node i to the root and
   insert item into its proper place */
   int grandparent = i / 4;
   while(grandparent)
      if(item.key > heap[grandparent].key){
         heap[i] = heap[grandparent];
         i = grandparent;
         grandparent /= 4;
      }
      else
         break;
   heap[i] = item;
}

Program 9.3 : Function to delete the element with minimum key

element delete_min(element heap[], int *n){
/* delete the minimum element from the min-max heap */
   int i, last, k, parent;
   element temp, x;

   if(!(*n)){
      fprintf(stderr, "The heap is empty\n");
      heap[0].key = INT_MAX; /* error key in heap[0] */
      return heap[0];
   }
   heap[0] = heap[1]; /* save the element */
   x = heap[(*n)--];
   /* find place to insert x */
   for(i = 1, last = (*n) / 2; i <= last;){
      k = min_child_grandchild(i, *n);
      if(x.key <= heap[k].key) break;
      /* case 2(b) or 2(c) */
      heap[i] = heap[k];
      if(k <= 2 * i + 1){ /* 2(b) */
         i = k;
         break;
      }
      /* case 2(c), k is a grandchild of i */
      parent = k/2;
      if(x.key > heap[parent].key)
         SWAP(heap[parent], x, temp);
      i = k;
   } /* for */
   heap[i] = x;
   return heap[0];
}

9.2 Deaps

Program 9.4 : Function to insert an item into a deap

void deap_insert(element deap[], int *n, element x){
/* insert x into the deap */
   int i;
   (*n)++;
   if(*n == MAX_SIZE){
      fprintf(stderr, "The heap is full\n");
      exit(1);
   }
   if(*n == 2)
      deap[2] = x; /* insert into empty deap */
   else switch(max_heap(*n)){
      case FALSE: /* *n is a position on min side */
         i = max_partner(*n);
         if(x.key > deap[i].key){
            deap[*n] = deap[i];
            max_insert(deap, i, x);
         }
         else
            min_insert(deap, *n, x);
         break;
      case TRUE: /* *n is a position on max side */
         i = min_partner(*n);
         if(x.key < deap[i].key){
            deap[*n] = deap[i];
            min_insert(deap, i, x);
         }
         else
            max_insert(deap, *n, x);
   }
}

Program 9.5 : Delete min function

element deap_delete_min(element deap[], int *n){
/* delete the minimum element form the heap */
   int i, j;
   element temp;
   if(*n < 2){
      fprintf(stderr, "The deap is empty\n");
      /* return an error code to user */
      deap[0].key = INT_MAX;
      return deap[0];
   }
   deap[0] = deap[2]; /* save min element */
   temp = deap[(*n)--];
   for(i = 2; i * 2 <= *n; deap[i] = deap[j], i = j){
      /* find node with smaller key */
      j = i * 2;
      if(j + 1 <= *n){
         if(deap[j].key > deap[j + 1].key)
            j++;
      }
   }
   modified_deap_insert(deap, i, temp);
   return deap[0];
}

9.3 Leftist Trees