I am wanting to create a heap array that does NOT use index 0, it will start at

Question

I am wanting to create a heap array that does NOT use index 0, it will start at 1. I would like to have some pseudo-code/example code in order to create an insert function, a remove function, an upHeap function and a downHeap function (upHeap will be called inside the insert function and downHeap will be called inside the remove function). I am provided with the following code:

//****** the following 2 function is in the header file **********

typedef char element[21];
typedef int priority;

typedef struct{
   priority p;
   element e;
} heap_content;

typedef struct{
   heap_content * arr;
   int array_size;   
   int heap_size;
   int next_level;   
} heapArray_type, *heapArray;

int size(heapArray heap);   
void insert(heapArray heap, heap_content content);
heap_content remove(heapArray heap);

//******* the following functions are the implementations *********

heapArray new_heapArray() {
   heapArray heap = (heapArray)malloc(sizeof(heapArray_type));
   heap->array_size = 2;
   heap->next_level = 2; //
   heap->heap_size = 0; //
   heap->arr = (heap_content *)malloc(sizeof(heap_content)*heap->array_size); //?
   return heap;
}

void delete_heapArray(heapArray heap){
   if(!heap) return;
   if(heap->arr) {delete heap->arr;}
   delete heap;
}

void resize_array(heapArray heap){
   heap_content* newArray = (heap_content *)malloc(sizeof(heap_content)*(heap->array_size + heap->next_level));
   std::memcpy(newArray, heap->arr, sizeof(heap_content)*heap->array_size); //copies heap->arr into newArray with a size of heap_content*heap->array_size
   heap->array_size += heap->next_level;
   heap->next_level *= 2;
   delete heap->arr;
   heap->arr = newArray;
}
// Heap - Array - ADT

void upHeap(){

}

void downHeap(){
}

int size(heapArray heap){
  
   return heap->array_size;
}

void insert(heapArray heap, heap_content content){

}

heap_content remove(heapArray heap){

}

Explanation / Answer

import java.io.*;
import java.util.*;
import java.lang.*;
import java.text.*;
public class heap
{
private Vector table;

public heap()
{ table = new Vector(); }

public heap(heap otherHeap)
{
table = new Vector();
int n = otherHeap.table.size();
for(int i = 0; i < n; i++)
add((Comparable)otherHeap.table.get(i));
}

public void clear()
{

table.clear();

}

public int size()
{

return table.size();

}
public void add(Comparable value)
{
int currentSize = table.size();
table.add(value);
upHeap(currentSize);
}

public Comparable remove()
{
Comparable hold = (Comparable)table.get(0);
int pos = table.size() - 1;
table.set(0, table.get(pos));
table.remove(pos);
if(table.size() > 0)
downHeap(0);
return hold;
}

public Comparable front()
  
{
return (Comparable)table.get(0);
  
}

public boolean empty()
{
return (table.size() == 0); }
private void downHeap( int i )
{
int size = table.size();
  
for( int child; ( child = leftChild( i ) ) < size; )
{
Comparable n1 = (Comparable) table.get( i );
Comparable n2 = (Comparable) table.get( child );

int rightChild = rightChild( i );
if( rightChild < size ) // check if there is a right child as well
{
    Comparable n3 = (Comparable) table.get( rightChild );
if( n2.compareTo( n3 ) < 0 )
{
  
child = rightChild;
n2 = n3;
}
}

  
if( n1.compareTo( n2 ) >= 0 )
break;
table.set( child, n1 );
table.set( i, n2 );

i = child; // start again with the child as current element
}
}
public static void main( String[] args )
{
try {
Heap heap = new Heap();
String test = "ThisIsATestStringToFindOutWhetherTheHeapWeJustBuildActuallyWorks";

System.out.println( test );
for( int idx = 0; idx < test.length(); idx++ )
heap.add( test.substring( idx, idx + 1 ) );
while( !heap.empty() )
{
Object obj = heap.remove();
System.out.print( obj );
}
System.out.println();
} catch( Exception ex ) {
ex.printStackTrace();
}
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.