How to optimize this data structure?

Question

Recently, I was asked to create a data structure that supports four operations, namely

• Click: add item to DS.
• Pop: delete the last pressed item.
• Find_max: Find the maximum element of the currently saved elements.
• Pop_max: remove the maximum element from DS.

Elements are integers.

Here is the solution I suggested:

• Take the stack.
• Save a couple of elements in it. The pair should be (element, max_so_far), where the element is the element in this index, and max_so_far is the element with the maximum rating that I have seen so far.
• By pushing an item onto the stack, check max_so_far of the topmost item in the stack. If the current number is greater than this, put the current value of the max_so_far pair as the current value of the element, otherwise save the previous max_so_far. This means that pressing will just be done by O(1) .
• For pop just pop item from the stack. Again, this operation is O(1) .
• For Find_max return the max_so_far value of the topmost item in the stack. Again, O(1) .
• Trying to maximize an element would include going through the stack and explicitly deleting the max element and dropping the elements on top of it after allocating new max_so_far values. It will be linear.

I was asked to improve it, but I could not.

In terms of time complexity, the total time can be improved if all operations occur in O(logn) , I think. How to do this, I can’t get.

Answer 1

One approach is to store pointers to items in a doubly linked list, as well as in the max-heap data structure (sorted by value).

Each element will retain its position in the doubly linked list, as well as in the max heap.

In this case, for all your operations it will take O (1) time in a doubly linked list, plus O (log (n)) time in the heap data structure.

Answer 2

One way to get O (log n) operations is to crush two data structures, in this case the list and priority queue are twice connected (a bunch of pairing is a good choice). We have a node structure like

 struct Node { Node *previous, *next; // doubly linked list Node **back, *child, *sibling; // pairing heap int value; } list_head, *heap_root; 

Now, to click, we insert both frames. To find_max, we return the value of the root of the pairing heap. For pop or pop_max, we exit the corresponding data structure and then use other node pointers to delete in another data structure.

Answer 3

Usually, when you need to find elements by quality A (value), as well as by quality B (insertion order), then you start looking for a data structure that actually has two data structures inside each other’s link, or else alternating .

For example: two cards whose keys are quality A and quality B, which values ​​are a common pointer to a structure containing iterators, to both cards and a value. Then you have log (n) to find the element through any quality, and erase ~ O (logn) to remove two iterators from any of the maps.

 struct hybrid { struct value { std::map<std::string, std::shared_ptr<value>>::iterator name_iter; std::map<int, std::shared_ptr<value>>::iterator height_iter; mountain value; }; std::map<std::string, std::shared_ptr<value>> name_map; std::map<int, std::shared_ptr<value>> height_map; mountain& find_by_name(std::string s) {return name_map[s]->value;} mountain& find_by_height(int height h) {return height_map[s]->value;} void erase_by_name(std::string s) { value& v = name_map[s]; name_map.erase(v.name_iter); height_iter.erase(v.height_iter); //note that this invalidates the reference v } }; 

However, in your case, you can do even better than this O (logn), since you only need the “latest” and “highest”. To quickly perform pop-height, you need a quick way to determine the next maximum, which means it needs to be calculated beforehand when pasting. To find the height position relative to the rest, you need some kind of map. To quickly pop, you need a quick way to find the next, last, but trivially calculated. I would recommend creating a map or a bunch of nodes, where the keys are the value to find max and the values ​​are a pointer to the next last value. This gives you an embedding of O (logn), O (1) to find the latest, O (1) or O (logn) to find the maximum value (depending on implementation) and erasing ~ O (logn) using any index.

Answer 4

Another way to do this: -

Create the maximum heap with elements. Thus, we can get / remove the max-element in O (1) operations. Along with this, we can maintain a pointer to the last clicked item. And as far as I know, deletion in heaps can be built in O (log n).