Diseñe una estructura de datos para las siguientes operaciones. La estructura de datos debe ser lo suficientemente eficiente para acomodar las operaciones de acuerdo con su frecuencia.
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.
Una solución simple es mantener una array ordenada donde el elemento más pequeño está en la primera posición y el elemento más grande está al final. La complejidad temporal de findMin(), findMAx() y deleteMax() es O(1). Pero las complejidades de tiempo de deleteMin(), insert() y delete() serán O(n).
¿Podemos hacer las dos operaciones más frecuentes en el tiempo O(1) y otras operaciones en el tiempo O(Logn)? .
La idea es usar dos montones binarios (uno máximo y uno mínimo). El principal desafío es que, al eliminar un elemento, debemos eliminarlo tanto del montón mínimo como del montón máximo. Entonces, necesitamos algún tipo de estructura de datos mutuos. En el siguiente diseño, hemos utilizado una lista doblemente enlazada como estructura de datos mutuos. La lista doblemente enlazada contiene todos los elementos de entrada e índices de los Nodes de almacenamiento dinámico mínimo y máximo correspondientes. Los Nodes de montones mínimos y máximos almacenan direcciones de Nodes de lista doblemente enlazada. El Node raíz del montón mínimo almacena la dirección del elemento mínimo en una lista doblemente enlazada. De manera similar, la raíz del montón máximo almacena la dirección del elemento máximo en una lista doblemente vinculada. Los siguientes son los detalles de las operaciones.
1) findMax(): Obtenemos la dirección del Node de valor máximo desde la raíz de Max Heap. Así que esta es una operación O(1).
1) findMin(): Obtenemos la dirección del Node de valor mínimo desde la raíz de Min Heap. Así que esta es una operación O(1).
3) deleteMin() : Obtenemos la dirección del Node de valor mínimo desde la raíz de Min Heap. Usamos esta dirección para encontrar el Node en una lista doblemente enlazada. De la lista doblemente enlazada, obtenemos el Node de Max Heap. Eliminamos el Node de los tres. Podemos eliminar un Node de la lista doblemente enlazada en tiempo O (1). Las operaciones de eliminación() para montones máximos y mínimos toman tiempo O (Inicio de sesión).
4) deleteMax() : es similar a deleteMin()
5) Insert() Siempre insertamos al principio de la lista enlazada en tiempo O(1). Insertar la dirección en Max y Min Heaps toma tiempo O (Logn). Entonces la complejidad general es O (Iniciar sesión)
6) Eliminar() Primero buscamos el elemento en la Lista vinculada. Una vez que se encuentra el elemento en tiempo O(n), lo eliminamos de la lista vinculada. Luego, usando los índices almacenados en la lista vinculada, lo eliminamos de Min Heap y Max Heaps en tiempo O (Logn). Entonces, la complejidad general de esta operación es O (n). La operación Eliminar se puede optimizar a O (Inicio de sesión) mediante el uso de un árbol de búsqueda binario equilibrado en lugar de una lista doblemente enlazada como estructura de datos mutuos. El uso de la búsqueda binaria balanceada no afectará la complejidad del tiempo de otras operaciones, ya que actuará como una estructura de datos mutuos como una lista doblemente enlazada.
A continuación se muestra la implementación en C de la estructura de datos anterior.
// 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;
}
}
// 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);
}
// 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 \n", findMax(myDS));
printf("Minimum = %d \n\n", findMin(myDS));
deleteMax(myDS); // 50 is deleted
printf("After deleteMax()\n");
printf("Maximum = %d \n", findMax(myDS));
printf("Minimum = %d \n\n", findMin(myDS));
deleteMin(myDS); // 10 is deleted
printf("After deleteMin()\n");
printf("Maximum = %d \n", findMax(myDS));
printf("Minimum = %d \n\n", findMin(myDS));
Delete(myDS, 40); // 40 is deleted
printf("After Delete()\n");
printf("Maximum = %d \n", findMax(myDS));
printf("Minimum = %d \n", findMin(myDS));
return 0;
}
Producción:
Maximum = 50 Minimum = 10 After deleteMax() Maximum = 40 Minimum = 10 After deleteMin() Maximum = 40 Minimum = 20 After Delete() Maximum = 30 Minimum = 20
Este artículo fue compilado por Aashish Barnwal y revisado por el equipo de GeeksforGeeks. Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA