I NEED THIS SOLVED QUICK AS POSSIBLE PLEASE Imagine that you are designing an ap
ID: 3681402 • Letter: I
Question
I NEED THIS SOLVED QUICK AS POSSIBLE PLEASE
Imagine that you are designing an application where you need to perform the operations Insert, Delete Maximum, and Delete Minimum. For this application, the cost of inserting is not important, because it can be done off-line prior to startup of the time-critical section, but the performance of the two deletion operations are critical. Repeated deletions of either kind must work as fast as possible. Suggest a data structure that can support this application, and justify your suggestion. What is the time complexity for each of the three key operations?
Explanation / Answer
The data structure that will give the best time complexity is Heap.We will use two heaps :Max Heap and Min Heap.
The main challenge is, while deleting an item, we need to delete from both min-heap and max-heap. So, we need some kind of mutual data structure. In the following design, we have used doubly linked list as a mutual data structure. We have used doubly linked list because it takes O(1) time to perform delete operation.The doubly linked list contains all input items and indexes of corresponding min and max heap nodes. The nodes of min and max heaps store addresses of nodes of doubly linked list. The root node of min heap stores the address of minimum item in doubly linked list. Similarly, root of max heap stores address of maximum item in doubly linked list. Following are the details of operations.
1) findMax(): We get the address of maximum value node from root of Max Heap. So this is a O(1) operation.
2) findMin(): We get the address of minimum value node from root of Min Heap. So this is a O(1) operation.
3) deleteMin(): We get the address of minimum value node from root of Min Heap. We use this address to find the node in doubly linked list. From the doubly linked list, we get node of Max Heap. We delete node from all three. We can delete a node from doubly linked list in O(1) time. delete() operations for max and min heaps take O(Logn) time.
4) deleteMax(): is similar to deleteMin()
5) Insert() We always insert at the beginning of linked list in O(1) time. Inserting the address in Max and Min Heaps take O(Logn) time. So overall complexity is O(Logn)
C Implementation of the above data structure:
// C program for efficient data structure
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A node of doubly linked list
struct LNode
{
int data;
int minHeapIndex;
int maxHeapIndex;
struct LNode *next, *prev;
};
// Structure for a doubly linked list
struct List
{
struct LNode *head;
};
// Structure for min heap
struct MinHeap
{
int size;
int capacity;
struct LNode* *array;
};
// Structure for max heap
struct MaxHeap
{
int size;
int capacity;
struct LNode* *array;
};
// The required data structure
struct MyDS
{
struct MinHeap* minHeap;
struct MaxHeap* maxHeap;
struct List* list;
};
// Function to swap two integers
void swapData(int* a, int* b)
{ int t = *a; *a = *b; *b = t; }
// Function to swap two List nodes
void swapLNode(struct LNode** a, struct LNode** b)
{ struct LNode* t = *a; *a = *b; *b = t; }
// A utility function to create a new List node
struct LNode* newLNode(int data)
{
struct LNode* node =
(struct LNode*) malloc(sizeof(struct LNode));
node->minHeapIndex = node->maxHeapIndex = -1;
node->data = data;
node->prev = node->next = NULL;
return node;
}
// Utility function to create a max heap of given capacity
struct MaxHeap* createMaxHeap(int capacity)
{
struct MaxHeap* maxHeap =
(struct MaxHeap*) malloc(sizeof(struct MaxHeap));
maxHeap->size = 0;
maxHeap->capacity = capacity;
maxHeap->array =
(struct LNode**) malloc(maxHeap->capacity * sizeof(struct LNode*));
return maxHeap;
}
// Utility function to create a min heap of given capacity
struct MinHeap* createMinHeap(int capacity)
{
struct MinHeap* minHeap =
(struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array =
(struct LNode**) malloc(minHeap->capacity * sizeof(struct LNode*));
return minHeap;
}
// Utility function to create a List
struct List* createList()
{
struct List* list =
(struct List*) malloc(sizeof(struct List));
list->head = NULL;
return list;
}
// Utility function to create the main data structure
// with given capacity
struct MyDS* createMyDS(int capacity)
{
struct MyDS* myDS =
(struct MyDS*) malloc(sizeof(struct MyDS));
myDS->minHeap = createMinHeap(capacity);
myDS->maxHeap = createMaxHeap(capacity);
myDS->list = createList();
return myDS;
}
// Some basic operations for heaps and List
int isMaxHeapEmpty(struct MaxHeap* heap)
{ return (heap->size == 0); }
int isMinHeapEmpty(struct MinHeap* heap)
{ return heap->size == 0; }
int isMaxHeapFull(struct MaxHeap* heap)
{ return heap->size == heap->capacity; }
int isMinHeapFull(struct MinHeap* heap)
{ return heap->size == heap->capacity; }
int isListEmpty(struct List* list)
{ return !list->head; }
int hasOnlyOneLNode(struct List* list)
{ return !list->head->next && !list->head->prev; }
// The standard minheapify function. The only thing it does extra
// is swapping indexes of heaps inside the List
void minHeapify(struct MinHeap* minHeap, int index)
{
int smallest, left, right;
smallest = index;
left = 2 * index + 1;
right = 2 * index + 2;
if ( minHeap->array[left] &&
left < minHeap->size &&
minHeap->array[left]->data < minHeap->array[smallest]->data
)
smallest = left;
if ( minHeap->array[right] &&
right < minHeap->size &&
minHeap->array[right]->data < minHeap->array[smallest]->data
)
smallest = right;
if (smallest != index)
{
// First swap indexes inside the List using address
// of List nodes
swapData(&(minHeap->array[smallest]->minHeapIndex),
&(minHeap->array[index]->minHeapIndex));
// Now swap pointers to List nodes
swapLNode(&minHeap->array[smallest],
&minHeap->array[index]);
// Fix the heap downward
minHeapify(minHeap, smallest);
}
}
// The standard maxHeapify function. The only thing it does extra
// is swapping indexes of heaps inside the List
void maxHeapify(struct MaxHeap* maxHeap, int index)
{
int largest, left, right;
largest = index;
left = 2 * index + 1;
right = 2 * index + 2;
if ( maxHeap->array[left] &&
left < maxHeap->size &&
maxHeap->array[left]->data > maxHeap->array[largest]->data
)
largest = left;
if ( maxHeap->array[right] &&
right < maxHeap->size &&
maxHeap->array[right]->data > maxHeap->array[largest]->data
)
largest = right;
if (largest != index)
{
// First swap indexes inside the List using address
// of List nodes
swapData(&maxHeap->array[largest]->maxHeapIndex,
&maxHeap->array[index]->maxHeapIndex);
// Now swap pointers to List nodes
swapLNode(&maxHeap->array[largest],
&maxHeap->array[index]);
// Fix the heap downward
maxHeapify(maxHeap, largest);
}
}
// Standard function to insert an item in Min Heap
void insertMinHeap(struct MinHeap* minHeap, struct LNode* temp)
{
if (isMinHeapFull(minHeap))
return;
++minHeap->size;
int i = minHeap->size - 1;
while (i && temp->data < minHeap->array[(i - 1) / 2]->data )
{
minHeap->array[i] = minHeap->array[(i - 1) / 2];
minHeap->array[i]->minHeapIndex = i;
i = (i - 1) / 2;
}
minHeap->array[i] = temp;
minHeap->array[i]->minHeapIndex = i;
}
// Standard function to insert an item in Max Heap
void insertMaxHeap(struct MaxHeap* maxHeap, struct LNode* temp)
{
if (isMaxHeapFull(maxHeap))
return;
++maxHeap->size;
int i = maxHeap->size - 1;
while (i && temp->data > maxHeap->array[(i - 1) / 2]->data )
{
maxHeap->array[i] = maxHeap->array[(i - 1) / 2];
maxHeap->array[i]->maxHeapIndex = i;
i = (i - 1) / 2;
}
maxHeap->array[i] = temp;
maxHeap->array[i]->maxHeapIndex = i;
}
// Function to find minimum value stored in the main data structure
int findMin(struct MyDS* myDS)
{
if (isMinHeapEmpty(myDS->minHeap))
return INT_MAX;
return myDS->minHeap->array[0]->data;
}
// Function to find maximum value stored in the main data structure
int findMax(struct MyDS* myDS)
{
if (isMaxHeapEmpty(myDS->maxHeap))
return INT_MIN;
return myDS->maxHeap->array[0]->data;
}
// A utility function to remove an item from linked list
void removeLNode(struct List* list, struct LNode** temp)
{
if (hasOnlyOneLNode(list))
list->head = NULL;
else if (!(*temp)->prev) // first node
{
list->head = (*temp)->next;
(*temp)->next->prev = NULL;
}
// any other node including last
else
{
(*temp)->prev->next = (*temp)->next;
// last node
if ((*temp)->next)
(*temp)->next->prev = (*temp)->prev;
}
free(*temp);
*temp = NULL;
}
// Function to delete maximum value stored in the main data structure
void deleteMax(struct MyDS* myDS)
{
MinHeap *minHeap = myDS->minHeap;
MaxHeap *maxHeap = myDS->maxHeap;
if (isMaxHeapEmpty(maxHeap))
return;
struct LNode* temp = maxHeap->array[0];
// delete the maximum item from maxHeap
maxHeap->array[0] =
maxHeap->array[maxHeap->size - 1];
--maxHeap->size;
maxHeap->array[0]->maxHeapIndex = 0;
maxHeapify(maxHeap, 0);
// remove the item from minHeap
minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;
minHeapify(minHeap, temp->minHeapIndex);
// remove the node from List
removeLNode(myDS->list, &temp);
}
// Function to delete minimum value stored in the main data structure
void deleteMin(struct MyDS* myDS)
{
MinHeap *minHeap = myDS->minHeap;
MaxHeap *maxHeap = myDS->maxHeap;
if (isMinHeapEmpty(minHeap))
return;
struct LNode* temp = minHeap->array[0];
// delete the minimum item from minHeap
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeap->array[0]->minHeapIndex = 0;
minHeapify(minHeap, 0);
// remove the item from maxHeap
maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
--maxHeap->size;
maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;
maxHeapify(maxHeap, temp->maxHeapIndex);
// remove the node from List
removeLNode(myDS->list, &temp);
}
// Function to enList an item to List
void insertAtHead(struct List* list, struct LNode* temp)
{
if (isListEmpty(list))
list->head = temp;
else
{
temp->next = list->head;
list->head->prev = temp;
list->head = temp;
}
}
// C program for efficient data structure
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// A node of doubly linked list
struct LNode
{
int data;
int minHeapIndex;
int maxHeapIndex;
struct LNode *next, *prev;
};
// Structure for a doubly linked list
struct List
{
struct LNode *head;
};
// Structure for min heap
struct MinHeap
{
int size;
int capacity;
struct LNode* *array;
};
// Structure for max heap
struct MaxHeap
{
int size;
int capacity;
struct LNode* *array;
};
// The required data structure
struct MyDS
{
struct MinHeap* minHeap;
struct MaxHeap* maxHeap;
struct List* list;
};
// Function to swap two integers
void swapData(int* a, int* b)
{ int t = *a; *a = *b; *b = t; }
// Function to swap two List nodes
void swapLNode(struct LNode** a, struct LNode** b)
{ struct LNode* t = *a; *a = *b; *b = t; }
// A utility function to create a new List node
struct LNode* newLNode(int data)
{
struct LNode* node =
(struct LNode*) malloc(sizeof(struct LNode));
node->minHeapIndex = node->maxHeapIndex = -1;
node->data = data;
node->prev = node->next = NULL;
return node;
}
// Utility function to create a max heap of given capacity
struct MaxHeap* createMaxHeap(int capacity)
{
struct MaxHeap* maxHeap =
(struct MaxHeap*) malloc(sizeof(struct MaxHeap));
maxHeap->size = 0;
maxHeap->capacity = capacity;
maxHeap->array =
(struct LNode**) malloc(maxHeap->capacity * sizeof(struct LNode*));
return maxHeap;
}
// Utility function to create a min heap of given capacity
struct MinHeap* createMinHeap(int capacity)
{
struct MinHeap* minHeap =
(struct MinHeap*) malloc(sizeof(struct MinHeap));
minHeap->size = 0;
minHeap->capacity = capacity;
minHeap->array =
(struct LNode**) malloc(minHeap->capacity * sizeof(struct LNode*));
return minHeap;
}
// Utility function to create a List
struct List* createList()
{
struct List* list =
(struct List*) malloc(sizeof(struct List));
list->head = NULL;
return list;
}
// Utility function to create the main data structure
// with given capacity
struct MyDS* createMyDS(int capacity)
{
struct MyDS* myDS =
(struct MyDS*) malloc(sizeof(struct MyDS));
myDS->minHeap = createMinHeap(capacity);
myDS->maxHeap = createMaxHeap(capacity);
myDS->list = createList();
return myDS;
}
// Some basic operations for heaps and List
int isMaxHeapEmpty(struct MaxHeap* heap)
{ return (heap->size == 0); }
int isMinHeapEmpty(struct MinHeap* heap)
{ return heap->size == 0; }
int isMaxHeapFull(struct MaxHeap* heap)
{ return heap->size == heap->capacity; }
int isMinHeapFull(struct MinHeap* heap)
{ return heap->size == heap->capacity; }
int isListEmpty(struct List* list)
{ return !list->head; }
int hasOnlyOneLNode(struct List* list)
{ return !list->head->next && !list->head->prev; }
// The standard minheapify function. The only thing it does extra
// is swapping indexes of heaps inside the List
void minHeapify(struct MinHeap* minHeap, int index)
{
int smallest, left, right;
smallest = index;
left = 2 * index + 1;
right = 2 * index + 2;
if ( minHeap->array[left] &&
left < minHeap->size &&
minHeap->array[left]->data < minHeap->array[smallest]->data
)
smallest = left;
if ( minHeap->array[right] &&
right < minHeap->size &&
minHeap->array[right]->data < minHeap->array[smallest]->data
)
smallest = right;
if (smallest != index)
{
// First swap indexes inside the List using address
// of List nodes
swapData(&(minHeap->array[smallest]->minHeapIndex),
&(minHeap->array[index]->minHeapIndex));
// Now swap pointers to List nodes
swapLNode(&minHeap->array[smallest],
&minHeap->array[index]);
// Fix the heap downward
minHeapify(minHeap, smallest);
}
}
// The standard maxHeapify function. The only thing it does extra
// is swapping indexes of heaps inside the List
void maxHeapify(struct MaxHeap* maxHeap, int index)
{
int largest, left, right;
largest = index;
left = 2 * index + 1;
right = 2 * index + 2;
if ( maxHeap->array[left] &&
left < maxHeap->size &&
maxHeap->array[left]->data > maxHeap->array[largest]->data
)
largest = left;
if ( maxHeap->array[right] &&
right < maxHeap->size &&
maxHeap->array[right]->data > maxHeap->array[largest]->data
)
largest = right;
if (largest != index)
{
// First swap indexes inside the List using address
// of List nodes
swapData(&maxHeap->array[largest]->maxHeapIndex,
&maxHeap->array[index]->maxHeapIndex);
// Now swap pointers to List nodes
swapLNode(&maxHeap->array[largest],
&maxHeap->array[index]);
// Fix the heap downward
maxHeapify(maxHeap, largest);
}
}
// Standard function to insert an item in Min Heap
void insertMinHeap(struct MinHeap* minHeap, struct LNode* temp)
{
if (isMinHeapFull(minHeap))
return;
++minHeap->size;
int i = minHeap->size - 1;
while (i && temp->data < minHeap->array[(i - 1) / 2]->data )
{
minHeap->array[i] = minHeap->array[(i - 1) / 2];
minHeap->array[i]->minHeapIndex = i;
i = (i - 1) / 2;
}
minHeap->array[i] = temp;
minHeap->array[i]->minHeapIndex = i;
}
// Standard function to insert an item in Max Heap
void insertMaxHeap(struct MaxHeap* maxHeap, struct LNode* temp)
{
if (isMaxHeapFull(maxHeap))
return;
++maxHeap->size;
int i = maxHeap->size - 1;
while (i && temp->data > maxHeap->array[(i - 1) / 2]->data )
{
maxHeap->array[i] = maxHeap->array[(i - 1) / 2];
maxHeap->array[i]->maxHeapIndex = i;
i = (i - 1) / 2;
}
maxHeap->array[i] = temp;
maxHeap->array[i]->maxHeapIndex = i;
}
// Function to find minimum value stored in the main data structure
int findMin(struct MyDS* myDS)
{
if (isMinHeapEmpty(myDS->minHeap))
return INT_MAX;
return myDS->minHeap->array[0]->data;
}
// Function to find maximum value stored in the main data structure
int findMax(struct MyDS* myDS)
{
if (isMaxHeapEmpty(myDS->maxHeap))
return INT_MIN;
return myDS->maxHeap->array[0]->data;
}
// A utility function to remove an item from linked list
void removeLNode(struct List* list, struct LNode** temp)
{
if (hasOnlyOneLNode(list))
list->head = NULL;
else if (!(*temp)->prev) // first node
{
list->head = (*temp)->next;
(*temp)->next->prev = NULL;
}
// any other node including last
else
{
(*temp)->prev->next = (*temp)->next;
// last node
if ((*temp)->next)
(*temp)->next->prev = (*temp)->prev;
}
free(*temp);
*temp = NULL;
}
// Function to delete maximum value stored in the main data structure
void deleteMax(struct MyDS* myDS)
{
MinHeap *minHeap = myDS->minHeap;
MaxHeap *maxHeap = myDS->maxHeap;
if (isMaxHeapEmpty(maxHeap))
return;
struct LNode* temp = maxHeap->array[0];
// delete the maximum item from maxHeap
maxHeap->array[0] =
maxHeap->array[maxHeap->size - 1];
--maxHeap->size;
maxHeap->array[0]->maxHeapIndex = 0;
maxHeapify(maxHeap, 0);
// remove the item from minHeap
minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;
minHeapify(minHeap, temp->minHeapIndex);
// remove the node from List
removeLNode(myDS->list, &temp);
}
// Function to delete minimum value stored in the main data structure
void deleteMin(struct MyDS* myDS)
{
MinHeap *minHeap = myDS->minHeap;
MaxHeap *maxHeap = myDS->maxHeap;
if (isMinHeapEmpty(minHeap))
return;
struct LNode* temp = minHeap->array[0];
// delete the minimum item from minHeap
minHeap->array[0] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeap->array[0]->minHeapIndex = 0;
minHeapify(minHeap, 0);
// remove the item from maxHeap
maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];
--maxHeap->size;
maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;
maxHeapify(maxHeap, temp->maxHeapIndex);
// remove the node from List
removeLNode(myDS->list, &temp);
}
// Function to enList an item to List
void insertAtHead(struct List* list, struct LNode* temp)
{
if (isListEmpty(list))
list->head = temp;
else
{
temp->next = list->head;
list->head->prev = temp;
list->head = temp;
}
}
void Insert(struct MyDS* myDS, int data)
{
struct LNode* temp = newLNode(data);
// insert the item in List
insertAtHead(myDS->list, temp);
// insert the item in min heap
insertMinHeap(myDS->minHeap, temp);
// insert the item in max heap
insertMaxHeap(myDS->maxHeap, temp);
}
// Driver program to test above functions
int main()
{
struct MyDS *myDS = createMyDS(10);
// Test Case #1
/*Insert(myDS, 10);
Insert(myDS, 2);
Insert(myDS, 32);
Insert(myDS, 40);
Insert(myDS, 5);*/
// Test Case #2
Insert(myDS, 10);
Insert(myDS, 20);
Insert(myDS, 30);
Insert(myDS, 40);
Insert(myDS, 50);
printf("Maximum = %d ", findMax(myDS));
printf("Minimum = %d ", findMin(myDS));
deleteMax(myDS); // 50 is deleted
printf("After deleteMax() ");
printf("Maximum = %d ", findMax(myDS));
printf("Minimum = %d ", findMin(myDS));
deleteMin(myDS); // 10 is deleted
printf("After deleteMin() ");
printf("Maximum = %d ", findMax(myDS));
printf("Minimum = %d ", findMin(myDS));
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.