Question

2) Questions about standard ADT's and their implementations that we have studied, including asymptotic analysis of their operations under various implementations. A DougPriority Queue uses time (real numbers, not ints) for its priorities. The bigger the time of an item the more important it is. Describe a good time-efficient implementation of DougPriority Queue. What is the big performance of your implementation for the 2 most important operations. Show a picture of your implementation when the following 4 items are in your Doug Priority Queue: name=Bob,time=2.31 name=Jim, time=17.2 name=Bill, time=11.1 and name=Tom,time=22.

Answer 1

solution:

DougPriorityQueue can be implemented using max-heap with time as its key.

// find the following c code for implementing abstract max-heap and corresponding algorithm

// Note: in array representation of our tree. left child of ith node is at index 2 *i and right child will be at

2*i+1 index.

#include<stdio.h>
#include<stdlib.h>   // for calloc() function.

typedef struct Heap_node
{
    void* data;               // this data can store any type of data as void pointer is universal which can point to any data type.
    float key;
}heap_node;

typedef struct Heap{
   heap_node* arr;
   int n;
}heap;

void initializeMinHeap(heap* h,int size)
{
   h->arr = (heap_node*) calloc (sizeof(heap_node*),size);
   h->n = -1;                   // -1 representing empty heap.
}

void maxHeapifyUp(heap* h,int i)                    //making the ith index find its place to satisfy max-heap property
{
    if(i==0)                                        // base case when the element is root itself.
        return;
    else if(h->arr[i].key > h->arr[(i-1)/2].key)    // if not satisfying max-heap property, then swap with its parent.
    {
        heap_node temp = h->arr[i];
        h->arr[i] = h->arr[(i-1)/2];
        h->arr[(i-1)/2] = temp;
        maxHeapifyUp(h,(i-1)/2);                    // after swaping call recursively at the parent.
    }
}

void maxHeapifyDown(heap* h,int i)
{
    int largeIndex = i;
    if((2*i)>=h->n)                                 // base case when i is the leaf node.
        return;
    else
    {

        if(h->arr[2*i+1].key > h->arr[largeIndex].key) // finding the larger one among the children and parent itself
            largeIndex = 2*i+1;
        if(h->arr[2*i+2].key > h->arr[largeIndex].key)
            largeIndex = 2*i+2;
        if(largeIndex == i)                            // if the ith node is the largest then simply return.
            return;
        else{
            heap_node temp = h->arr[i];                 // else swap with the largest.
            h->arr[i] = h->arr[largeIndex];
            h->arr[largeIndex] = temp;
            maxHeapifyDown(h,largeIndex);               // call recursively at the swapped position.
        }

    }
}

void* extractMax(heap *h)
{
    void* temp = h->arr[0].data;                      
    if(h->n==-1)                                        // base case when heap is empty.
        return NULL;
    else{
        h->arr[0] = h->arr[h->n];                       // replace root with last element in heap array i.e some leaf node.
        --(h->n);
        maxHeapifyDown(h,0);                            // recursively heapify down to find its spot and retain the heap property.
    }
    return temp;                                        // return the value of the extracted one.
}

/* extractMax() is similar to dequeue() in max-heap as we need element with maximum key.
   This can be done in O(log n), where n is no.of elements in heap as we need to swap with log n levels
   after replacing the root with leaf node.*/

void maxHeapInsert(heap *h,void* data,float key)
{
    ++(h->n);                                           // updating heap size.
    h->arr[h->n].data = data;                           // inserting at the last.
    h->arr[h->n].key = key;
    maxHeapifyUp(h,h->n);                               // calling heapifyup to find its spot.
}

/* maxHeapInsert() will have time complexity of O(log n), as for searching for the right spot needs checking log n levels.

// Please refer above image for indentation.

Tree will be as follows after inserting the 4 elements in our DougPriorityQueue.

                                       Tom, time = 22
                                   /                 \
                           Jim, time = 17.2       Bill, time = 11.1
                               /
                           Bob, time = 2.31

please give me thumb up