Как мне спроектировать структуру данных, имеющую операции push () и popMin () с push () в O (log (n)) и popMin в постоянном времени, то есть O (1)?

Question

Мой собственный ответ - бинарное дерево поиска со следующим указателем, например:

 struct Node{
    int key;
    Node* left;
    Node* right;
    Node* next; 
    Node* parent;
};
typedef struct Node MyNode;
MyNode* myTable;
MyNode* leftNode;

Я прав, или есть какой-то другой ответ?

Answer 1

Вам нужна куча: https://en.wikipedia.org/wiki/Heap_(data_structure)

вставка O (logN) * ​​1005 *

найти мин. O (1)