Index Heap
=================================

Index heap is also called ``Indexed Priority Queue``. In an Indexed Priority Queue, data is stored just like standard priority queue and along with this, the value of a data can be updated using its key. It is called “indexed” because  a hash map can be used to store the index in container using the key of key-value pair input  as the key of hash map. This comes handy while implementing  Dijkstra’s Algorithm using min-heap. It can also be used in any other program where it is required to put key-value pairs in priority queue and along with it you need to update value of keys with push or pop function .

TopK Traded Stocks
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

You work in an electronic exchange. Throughout the day, you receive ticks (trading data) which consists of ticker symbol and its traded volume of stocks. Eg: {name: UBER, volume: 20}

What data structure will you maintain if you have to tell top k ticker traded by volume at runtime throughout the day. What's the most efficient solution that you can think of?

----

This is an index heap question. To avoid using more than one map, we create a new class to store stock information.

.. literalinclude:: index_heap.h
  :language: c++
  :linenos:
  :lines: 11-14

Then we implement this max heap binary tree:

.. literalinclude:: index_heap.h
  :language: c++
  :linenos:
  :lines: 16-91
  :emphasize-lines: 2-3, 9, 16, 57-76


In this problem, we cannot pop the top, so we have to use another extra priority queue to get the topK at runtime. The key idea is **to pop top element in the new heap, and add both of its children into the new heap**. `tk2idx` here is very important   to get the base array index from the ticker symbol.

|:alien:| A website logs all the ip address which visits its webpage(streaming data). How to display top 10 ip address at real time？