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 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 delete an item from List. The function also
// removes item from min and max heaps
void
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 structure
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);
}
// 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 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;
}