Homework SourseDescribe a data structure that supports both removeMin and r
Solution
The idea here is to use the concept of two binary heaps along with the concept of list(doubly linked list).
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.
1) findMin(): We get the address of minimum value node from root of Min Heap. So this is a O(1) operation.
3) removeMin(): 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) removeMax(): 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)
#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 CDS
{
struct MinHeap* minHeap;
struct MaxHeap* maxHeap;
struct List* list;
};
// 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 the main data structure
// with given capacity
struct CDS* createCDS(int capacity)
{
struct CDS* CDS =
(struct CDS*) malloc(sizeof(struct CDS));
CDS->minHeap = createMinHeap(capacity);
CDS->maxHeap = createMaxHeap(capacity);
CDS->list = createList();
return CDS;
}
// Some basic operations for heaps
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; }
// The standard minHeapop function. The only thing it does extra
// is swapping indexes of heaps inside the List
void minHeapop(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
minHeapop(minHeap, smallest);
}
}
// The standard maxHeapop function. The only thing it does extra
// is swapping indexes of heaps inside the List
void maxHeapop(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
maxHeapop(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 CDS* CDS)
{
if (isMinHeapEmpty(CDS->minHeap))
return INT_MAX;
return CDS->minHeap->array[0]->data;
}
// Function to find maximum value stored in the main data structure
int findMax(struct CDS* CDS)
{
if (isMaxHeapEmpty(CDS->maxHeap))
return INT_MIN;
return CDS->maxHeap->array[0]->data;
}
// Function to delete maximum value stored in the main data structure
void removeMax(struct CDS* CDS)
{
MinHeap *minHeap = CDS->minHeap;
MaxHeap *maxHeap = CDS->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;
maxHeapop(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;
minHeapop(minHeap, temp->minHeapIndex);
// remove the node from List
removeLNode(CDS->list, &temp);
}
// Function to delete minimum value stored in the main data structure
void removeMin(struct CDS* CDS)
{
MinHeap *minHeap = CDS->minHeap;
MaxHeap *maxHeap = CDS->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;
minHeapop(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;
maxHeapop(maxHeap, temp->maxHeapIndex);
// remove the node from List
removeLNode(CDS->list, &temp);
}
// Function to remove item from min and max heaps
void Delete(struct CDS* CDS, int item)
{
MinHeap *minHeap = CDS->minHeap;
MaxHeap *maxHeap = CDS->maxHeap;
// remove item from min heap
minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];
--minHeap->size;
minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;
minHeapop(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;
maxHeapop(maxHeap, temp->maxHeapIndex);
// remove node from List
removeLNode(CDS->list, &temp);
}
// insert operation for main data structure
void Insert(struct CDS* CDS, int data)
{
// insert the item in List
insertAtHead(CDS->list, temp);
// insert the item in min heap
insertMinHeap(CDS->minHeap, temp);
// insert the item in max heap
insertMaxHeap(CDS->maxHeap, temp);
}
Hope this illustration helps...
