Рубрики

Разработка эффективной структуры данных для заданных операций

Разработайте структуру данных для следующих операций. Структура данных должна быть достаточно эффективной, чтобы приспособить операции в соответствии с их частотой.

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. 

Простое решение состоит в том, чтобы поддерживать отсортированный массив, где наименьший элемент находится в первой позиции, а самый большой элемент — в конце. Временная сложность findMin (), findMAx () и deleteMax () равна O (1). Но временные сложности deleteMin (), insert () и delete () будут O (n).

Можем ли мы сделать наиболее частые две операции в O (1) и другие операции в O (Logn) времени? ,
Идея состоит в том, чтобы использовать две двоичные кучи (одна максимальная и одна минимальная куча). Основная проблема заключается в том, что при удалении элемента нам нужно удалить как из min-heap, так и из max-heap. Итак, нам нужна какая-то взаимная структура данных. В следующем дизайне мы использовали двусвязный список в качестве взаимной структуры данных. Двусвязный список содержит все входные элементы и индексы соответствующих узлов кучи min и max. Узлы кучи min и max хранят адреса узлов двусвязного списка. Корневой узел min heap хранит адрес минимального элемента в двусвязном списке. Аналогично, корень max heap хранит адрес максимального элемента в двусвязном списке. Ниже приведены подробности операций.

1) findMax (): мы получаем адрес узла максимального значения из корня Max Heap. Так что это операция O (1).

1) findMin (): мы получаем адрес узла минимального значения из корня Min Heap. Так что это операция O (1).

3) deleteMin () : мы получаем адрес узла минимального значения из корня Min Heap. Мы используем этот адрес, чтобы найти узел в двусвязном списке. Из двусвязного списка мы получаем узел Max Heap. Удаляем узел из всех трех. Мы можем удалить узел из двусвязного списка за O (1) раз. Операции delete () для кучи max и min занимают время O (Logn).

4) deleteMax () : аналогично deleteMin ()

5) Вставка () Мы всегда вставляем в начале связанного списка в O (1) раз. Вставка адреса в Max и Min Heaps занимает время O (Logn). Таким образом, общая сложность составляет O (Logn)

6) Удалить () Сначала мы ищем элемент в связанном списке. Как только элемент найден за O (n) время, мы удаляем его из связанного списка. Затем, используя индексы, хранящиеся в связанном списке, мы удаляем его из Min Heap и Max Heaps за O (Logn). Таким образом, общая сложность этой операции составляет O (n). Операцию удаления можно оптимизировать до O (Logn), используя сбалансированное двоичное дерево поиска вместо двусвязного списка в качестве взаимной структуры данных. Использование сбалансированного бинарного поиска не повлияет на временную сложность других операций, так как будет действовать как взаимная структура данных, такая как двусвязный список.

Ниже приведена реализация вышеуказанной структуры данных.

// C программа для эффективной структуры данных
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

  
// Узел двусвязного списка

struct LNode

{

    int data;

    int minHeapIndex;

    int maxHeapIndex;

    struct LNode *next, *prev;

};

  
// Структура для двусвязного списка

struct List

{

    struct LNode *head;

};

  
// Структура для минимальной кучи

struct MinHeap

{

    int size;

    int capacity;

    struct LNode* *array;

};

  
// Структура для максимальной кучи

struct MaxHeap

{

    int size;

    int capacity;

    struct LNode* *array;

};

  
// Требуемая структура данных

struct MyDS

{

    struct MinHeap* minHeap;

    struct MaxHeap* maxHeap;

    struct List* list;

};

  
// Функция для замены двух целых

void swapData(int* a, int* b)

{ int t = *a;   *a = *b;   *b = t; }

  
// Функция для замены двух узлов списка

void swapLNode(struct LNode** a, struct LNode** b)

{ struct LNode* t = *a; *a = *b; *b = t; }

  
// Вспомогательная функция для создания нового узла List

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;

}

  
// Сервисная функция для создания максимальной кучи заданной емкости

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;

}

  
// Служебная функция для создания минимальной кучи заданной емкости

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;

}

  
// Утилита для создания списка

struct List* createList()

{

    struct List* list =

      (struct List*) malloc(sizeof(struct List));

    list->head = NULL;

    return list;

}

  
// Сервисная функция для создания основной структуры данных
// с заданной емкостью

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;

}

  
// Некоторые основные операции с кучами и списком

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; }

  

  
// Стандартная функция minheapify. Единственное, что он делает дополнительно
// меняет местами индексы кучи внутри списка

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)

    {

        // Сначала меняем индексы внутри списка по адресу

        // списка узлов

        swapData(&(minHeap->array[smallest]->minHeapIndex),

                 &(minHeap->array[index]->minHeapIndex));

  

        // Теперь меняем указатели на узлы List

        swapLNode(&minHeap->array[smallest],

                  &minHeap->array[index]);

  

        // Исправляем кучу вниз

        minHeapify(minHeap, smallest);

    }

}

  
// Стандартная функция maxHeapify. Единственное, что он делает дополнительно
// меняет местами индексы кучи внутри списка

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)

    {

        // Сначала меняем индексы внутри списка по адресу

        // списка узлов

        swapData(&maxHeap->array[largest]->maxHeapIndex,

                 &maxHeap->array[index]->maxHeapIndex);

  

        // Теперь меняем указатели на узлы List

        swapLNode(&maxHeap->array[largest],

                  &maxHeap->array[index]);

  

        // Исправляем кучу вниз

        maxHeapify(maxHeap, largest);

    }

}

  
// Стандартная функция для вставки элемента в 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;

}

  
// Стандартная функция для вставки элемента в 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;

}

  

  
// Функция для поиска минимального значения, хранящегося в основной структуре данных

int findMin(struct MyDS* myDS)

{

    if (isMinHeapEmpty(myDS->minHeap))

        return INT_MAX;

  

    return myDS->minHeap->array[0]->data;

}

  
// Функция для поиска максимального значения, хранящегося в основной структуре данных

int findMax(struct MyDS* myDS)

{

    if (isMaxHeapEmpty(myDS->maxHeap))

        return INT_MIN;

  

    return myDS->maxHeap->array[0]->data;

}

  
// Утилита для удаления элемента из связанного списка

void removeLNode(struct List* list, struct LNode** temp)

{

    if (hasOnlyOneLNode(list))

        list->head = NULL;

  

    else if (!(*temp)->prev) // первый узел

    {

        list->head = (*temp)->next;

        (*temp)->next->prev = NULL;

    }

    // любой другой узел, включая последний

    else

    {

        (*temp)->prev->next = (*temp)->next;

        // последний узел

        if ((*temp)->next)

            (*temp)->next->prev = (*temp)->prev;

    }

    free(*temp);

    *temp = NULL;

}

  
// Функция для удаления максимального значения, хранящегося в основной структуре данных

void deleteMax(struct MyDS* myDS)

{

    MinHeap *minHeap = myDS->minHeap;

    MaxHeap *maxHeap = myDS->maxHeap;

  

    if (isMaxHeapEmpty(maxHeap))

        return;

    struct LNode* temp = maxHeap->array[0];

  

    // удаляем максимальный элемент из maxHeap

    maxHeap->array[0] =

        maxHeap->array[maxHeap->size - 1];

    --maxHeap->size;

    maxHeap->array[0]->maxHeapIndex = 0;

    maxHeapify(maxHeap, 0);

  

    // удаляем элемент из minHeap

    minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];

    --minHeap->size;

    minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;

    minHeapify(minHeap, temp->minHeapIndex);

  

    // удаляем узел из списка

    removeLNode(myDS->list, &temp);

}

  
// Функция для удаления минимального значения, хранящегося в основной структуре данных

void deleteMin(struct MyDS* myDS)

{

    MinHeap *minHeap = myDS->minHeap;

    MaxHeap *maxHeap = myDS->maxHeap;

  

    if (isMinHeapEmpty(minHeap))

        return;

    struct LNode* temp = minHeap->array[0];

  

    // удаляем минимальный элемент из minHeap

    minHeap->array[0] = minHeap->array[minHeap->size - 1];

    --minHeap->size;

    minHeap->array[0]->minHeapIndex = 0;

    minHeapify(minHeap, 0);

  

    // удаляем элемент из maxHeap

    maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];

    --maxHeap->size;

    maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;

    maxHeapify(maxHeap, temp->maxHeapIndex);

  

    // удаляем узел из списка

    removeLNode(myDS->list, &temp);

}

  
// Функция для включения элемента в список

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;

    }

}

  
// Функция для удаления элемента из списка. Функция также
// удаляет элемент из кучи min и max

void Delete(struct MyDS* myDS, int item)

{

    MinHeap *minHeap = myDS->minHeap;

    MaxHeap *maxHeap = myDS->maxHeap;

  

    if (isListEmpty(myDS->list))

        return;

  

    // поиск узла в списке

    struct LNode* temp = myDS->list->head;

    while (temp && temp->data != item)

        temp = temp->next;

  

    // если элемент не найден

    if (!temp || temp && temp->data != item)

        return;

  

    // удаляем элемент из минимальной кучи

    minHeap->array[temp->minHeapIndex] = minHeap->array[minHeap->size - 1];

    --minHeap->size;

    minHeap->array[temp->minHeapIndex]->minHeapIndex = temp->minHeapIndex;

    minHeapify(minHeap, temp->minHeapIndex);

  

    // удаляем элемент из максимальной кучи

    maxHeap->array[temp->maxHeapIndex] = maxHeap->array[maxHeap->size - 1];

    --maxHeap->size;

    maxHeap->array[temp->maxHeapIndex]->maxHeapIndex = temp->maxHeapIndex;

    maxHeapify(maxHeap, temp->maxHeapIndex);

  

    // удаляем узел из списка

    removeLNode(myDS->list, &temp);

}

  
// вставить операцию для основной структуры данных

void Insert(struct MyDS* myDS, int data)

{

    struct LNode* temp = newLNode(data);

  

    // вставляем элемент в список

    insertAtHead(myDS->list, temp);

  

    // вставляем элемент в минимальную кучу

    insertMinHeap(myDS->minHeap, temp);

  

    // вставляем элемент в максимальную кучу

    insertMaxHeap(myDS->maxHeap, temp);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    struct MyDS *myDS = createMyDS(10);

    // Тестовый пример № 1

    / * Вставить (myDS, 10);

    Вставить (myDS, 2);

    Вставить (myDS, 32);

    Вставить (myDS, 40);

    Вставить (myDS, 5); * /

  

    // Тестовый пример № 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 удалено

    printf("After deleteMax()\n");

    printf("Maximum = %d \n", findMax(myDS));

    printf("Minimum = %d \n\n", findMin(myDS));

  

    deleteMin(myDS); // 10 удалено

    printf("After deleteMin()\n");

    printf("Maximum = %d \n", findMax(myDS));

    printf("Minimum = %d \n\n", findMin(myDS));

  

    Delete(myDS, 40); // 40 удалено

    printf("After Delete()\n");

    printf("Maximum = %d \n", findMax(myDS));

    printf("Minimum = %d \n", findMin(myDS));

  

    return 0;

}

Выход:

Maximum = 50
Minimum = 10

After deleteMax()
Maximum = 40
Minimum = 10

After deleteMin()
Maximum = 40
Minimum = 20

After Delete()
Maximum = 30
Minimum = 20

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Разработка эффективной структуры данных для заданных операций

0.00 (0%) 0 votes