Intro to competitive programming - 3

Covered in this section:

• Priority Queue and it's STL
• Hashing, and STL

Priority Queue

It is a special type of queue in which each element is associated with a priority and is served according to its priority. Its is based on binary heap (will be dealt with later).

• Type: decribes the type of data structure present inside priority_queue, like int or ll or pair.
• cont: tells us what is the underlying container of queue, defaults to vector if not mentioned.

• comp: When you need to sort based on certain properties, we use comparative functions with two arguements a and b. It returns true if a is supposed to be before b in a vector. example: (Comparator to sort with respect to absolute value)

  
          bool cmp(int a, int b)
          {
              return abs(a) >= abs(b);
          }
          sort(v.begin(), v.end(), cmp);
      

C++ STL for priority queue

• push(): push element into the queue.
• pop(): delete the greatedt element in the queue.
• top(): obtain the greatest element of queue.

Important time complexities for priority queue

• Insert: O(1)
• Get Highest Priority (e.g., Max/Min): O(n)
• Remove Highest Priority: O(n)

Hash table

Hashing means associating a value with a key/index.

Hash tables are a type of data structure in which the key/index value of the data element is generated from a hash function. This enables very fast data access as the index value behaves as a key for the data value. This website shows a visualisation of hashing with seperate chaining.

In C++ hashing is used by unordered_map/unordered_set. Normal Map and set will be discussed later.