HEAPS


We can implement priority queues using d-heaps, which are d-ary trees. Here we will concentrate on 2-heaps, that is, heaps which are implemented using binary trees. A heap is a partially ordered tree with all levels full execpt possibly the last. In the bottom level items must be in the leftmost nodes. The height of 2-heap with n nodes is $\leq \lceil \log_d n \rceil$. The nodes of a d-heap can be stored in an array in breadth-first order. For any node with array index i its parent is at position $\lceil (i-1)/d\rceil$, and for any node i its children will have indices in the range [d(i-1)+2 .. di+1]. For a 2-heap these values are $\lfloor i/2 \rfloor$ and [2i .. 2i+1].
 

2-HEAP OPERATIONS

item findmin()   
   if  $h ~ = ~\{\} ~\rightarrow $   return null 
   |  $h \neq ~\{\} ~\rightarrow$  return  h[1] 
   fi  
end findmin 
 
 
void insert(item e)  
   n  :=  n + 1;     h[n]  :=   e 
   siftup(n)  
end insert  
 
 
heap makeheap(array s)  
   $h ~:= ~\{\}$;     n  :=  0 
   for  $e \in s ~\rightarrow$  
      n  :=  n+1;     h[n]  :=  e  
   rof 
   $j ~:= ~\lfloor n/2\rfloor$ 
   do  $j ~\gt ~0 ~\rightarrow $  
      siftdown(j);     $j -\! -$  
   od  
end  makeheap 
 
 
item delmin()  
   if  $h ~ = ~\{\} ~\rightarrow $  return  null fi 
   e  :=  h[1] 
   h[1]  :=   h[n - -] 
   siftdown(1)  
   return   e  
end delmin


2-HEAP OPERATIONS

void siftup(int i)  
   e  :=  h[i] 
   $p ~:= ~\lfloor i/2 \rfloor$ 
   do $p ~\neq ~0$  and  h[p].key  >  $e.key
 ~\rightarrow $ 
      h[i]  :=  h[p];     i  :=  p 
      $p := ~ \lfloor i/2 \rfloor$  
   od 
   h[i]  :=  e  
end siftup 
 
 
void siftdown(int i)  
   e  :=  h[i] 
   g  :=  minchild(i) 
   do $g ~\neq ~0$  and  h[g].key < e.key$ ~\rightarrow$  
      h[i]  :=  h[g];     i  :=  g 
      g  :=  minchild(i)  
   od  
   h[i]  :=  e  
end siftdown 
  
  
int minchild(int i)  
   if  $2i ~\gt ~n ~\rightarrow$   return  0 
   $\vert ~2i ~= ~n ~\rightarrow ~~{\bf return} ~ 2i$ 
   $\vert ~2i ~<~ n ~\rightarrow$  
      return  min_index{h[2i].key, h[2i + 1].key}  
   fi  
end minchild

Bernard Waxman
10/27/1997