Design an efficient data structure for given operations
1) findMin() : Returns the minimum item.
Frequency: Most frequent
2) findMax() : Returns the maximum item.
Frequency: Most frequent
3) deleteMin() : Delete the minimum item.
Frequency: Moderate frequent
4) deleteMax() : Delete the maximum item.
Frequency: Moderate frequent
5) Insert() : Inserts an item.
Frequency: Least frequent
6) Delete() : Deletes an item.
Frequency: Least frequent.
A simple solution is to maintain a sorted array where smallest element is at first position and largest element is at last. The time complexity of findMin(), findMAx() and deleteMax() is O(1). But time complexities of deleteMin(), insert() and delete() will be O(n).
Can we do the most frequent two operations in O(1) and other operations in O(Logn) time?.
The idea is to use two binary heaps (one max and one min heap):t we have used doubly linked list as a mutual data structure. 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.
The idea is to use two binary heaps (one max and one min heap):t we have used doubly linked list as a mutual data structure. 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.
struct LNode{ int data; int minHeapIndex; int maxHeapIndex; struct LNode *next, *prev;};// Structure for a doubly linked liststruct List{ struct LNode *head;};// Structure for min heapstruct MinHeap{ int size; int capacity; struct LNode* *array;};// Structure for max heapstruct MaxHeap{ int size; int capacity; struct LNode* *array;};// The required data structurestruct MyDS{ struct MinHeap* minHeap; struct MaxHeap* maxHeap; struct List* list;};// Function to delete an item from List. The function also// removes item from min and max heapsvoid Delete(struct MyDS* myDS, int item){ MinHeap *minHeap = myDS->minHeap; MaxHeap *maxHeap = myDS->maxHeap; if (isListEmpty(myDS->list)) return; // search the node in List struct LNode* temp = myDS->list->head; while (temp && temp->data != item) temp = temp->next; // if item not found if (!temp || temp && temp->data != item) return; // remove item from min heap minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex; minHeapify(minHeap, temp->minHeapIndex); // remove item from max heap maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1]; --maxHeap->size; maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex; maxHeapify(maxHeap, temp->maxHeapIndex); // remove node from List removeLNode(myDS->list, &temp);}// insert operation for main data structurevoid 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);}// Function to delete maximum value stored in the main data structurevoid 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 structurevoid 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 find minimum value stored in the main data structureint 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 structureint 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 listvoid 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;}