Data Structures for Coding Tests (2)

English edition note: Complexities depend on the implementation: balanced trees, average-case hash tables and worst-case hash behavior must be distinguished. Heap order also permits equal keys. The historical code examples are preserved; check C++ size formatting and the commented Python example before reuse.

#📖 Priority Queue

• Use this when data should be processed in priority order.
• Implemented using a heap.
• Insertion and deletion O(logN)
• Search O(N)

#What is a heap?

First, we need to understand heaps.

A heap is a data structure designed to find the node with the largest or smallest key in a complete binary tree.

• Max Heap
  • A heap in which a parent node has a larger key than its children.
  • Root node: the node with the largest key.
• Min Heap
  • A heap in which a parent node has a smaller key than its children.
  • Root node: the node with the smallest key.

#Using a priority queue in C++

C++ : max-heap

//C++
#include <iostream>
#include <queue>
using namespace std;

priority_queue<int> pq;
pq.push(7);
pq.push(5);
pq.push(4);
printf("size: %d\n", pq.size());
while(!pq.empty()){
  printf("%d\n", pq.top());   //Print the top value
  pq.pop();                   //Remove the top value without printing it
}

#Using a priority queue in Python

Python : min-heap

#Python
"""
#The alternative below is faster here because it avoids thread-safety overhead
from queue import PriorityQueue
q = PriorityQueue()
q.put(7)
q.put(5)
q.put(4)
print("size: ", q.qsize())
while not q.empty():
print(q.get())              #pop
"""
import heapq
heap = []
heapq.heappush(heap, 7)
heapq.heappush(heap, 5)
heapq.heappush(heap, 4)
print("size: ", len(heap))
while len(heap) > 0:
  print(heapq.heappop(heap))

#📖 Map (Dictionary)

• Stores data as key-value pairs.
  • Keys are unique.
• Insertion and deletion, Search O(logN)
• Keys cannot be duplicated.
• Retrieve a value using its key.
• A key-value pair is called an entry.

#Map implementations by language

Related explanations
red-black tree Blog explanation Wikipedia Operations take O(logN).
hash Blog explanation Operations take O(1).

#Using a map in C++

//C++
#include <iostream>
#include <map>
using namespace std;

map<string, int> m;
m["Jiho"] = 1;
m["love"] = 2;
m["bird"] = 3;
printf("size: %d\n", m.size());
for (auto p : m)
  printf("%s, %d\n", p.first.c_str(), p.second);

#Using a map in Python

#Python
m = {}
m["Jiho"] = 1
m["love"] = 2
m["bird"] = 3
print("size: ", len(m))
for key in m:
  print(key, m[key])

#📖 Set

• Stores distinct values.
• Insertion and deletion, Search O(logN)

remove(): deletion