Map ADT

Methods

• get(key)
• put(key, value)
• remove(key)
• size()
• isEmpty()
• entrySet()
• keySet()
• values()

Performance of a List-Based Map

• put : O(1), but if uniqueness needed, O(n).
• get, remove : O(n) in the worst case.

---

Hashing

Collision Handling

Seperate Chaining

• Let each cell in the table point to a linked list of entries that map there.
• Simple, but requires additional memory outside the table.

Linear Probing

• Open addressing : The colliding item is placed in a different cell of the table.
• Linear probing : 겹치면 다음 사용 가능한 칸에 대입한다.

Updates with Linear Probing

• if collided item is removed, the items with the same key value may not be accessible. TO handle insertion and deletions, we introduce AVAILABLE, which replaces deleted elements.
• 즉, 값을 제거하고 이 플래그를 저장해두면 다음 번 probing시에 이 플래그가 있거나 비어있는 칸을 인식하여 데이터 삽입 여부를 결정한다. 굳이 이렇게 해야되나..?

Double Hashing

• Secondary hash function d(k)를 사용한다.
  (h(k) + j * d(k)) mod N for j = 0, 1, ..., N - 1
• The table size N must be a prime to allow probing of all the cells.

Performance of Hashing

The Worst case time complexity on hash table

• Insertion : O(n)
• Deletion : O(n)
• The worst case occurs when all the keys inserted into the map collide.

Our expectation

• The load factor a = n / N affects the performance of a hash table.
• Assuming that the hash values are like random numbers, it can be shown that the expected number of probes for an insertion with open addressing is 1/(1-a)

---

Priority Queue ADT

Methods

• insert(k, x)
• deleteMax() or deleteMin()
• max() or min()
• size(), isEmpty()

---

Heap

Time complexity

• A heap has height O(log n)
• Insertion of a heap runs in O(loh n) time.

Methods

Insertion

public void insert(int priority) {
        int i;

        if (!isFull()) {
            heap[heapSize] = priority;
            i = heapSize++;
            
            while((i > 0) && (heap[(i-1)/2] < heap[i])) {
                swap(heap[i], heap[(i-1)/2]);
                i = (i-1) / 2;
            }
        }
    }

Delete Max

• Time complexity : O(log n)

---

Heap Sort

PQ Sort using a heap

public void heapSort(int[] A) {
	Heap H = new Heap();
    
    for (int i = 0; i < A.length; i++)
    	H.insert(A[i]);				// O(nlogn)
     
    for (int i = 0; i < A.length; i++)
    	A[i] = H.deleteMax();		// O(nlogn)
}

Algorithms

1. Build max-heap (or min-heap) from an unordered array.
2. Find the maximum (minimum) element at the root.
3. Exchange the root and the last node.
4. Remove the last node from heap and decrease heap size by 1.
5. Heapify.
6. Repeat the same procedure until the heap becomes empty.

• Heapsort is In-palce algorithm

Analysis

Consider a PQ with n items implemented by menas of a heap.

• Space complexity : O(n)
• insert, deleteMax : O(log n)
• size, isEmpty, max : O(1)

  using a heap based PQ, it can sort elements in O(nlogn) time.