Part Ⅰ
2 Linked Lists
The sentinel reference always points to a sentinel node.
Sentinel code make it easier to reason about code, and also give you specific goals to strive for in making sure your code works.
2.1 Singly Linked Lists
The first item (if it exists) is at sentinel.next.
No need to check for special cases since sentinel node is never null!
import java.util.Iterator;
public class SLList implements Iterable<Integer> {
public static class IntNode {
public int item;
public IntNode next;
public IntNode(int i, IntNode n) {
item = i;
next = n;
}
}
private final IntNode sentinel;
private int size;
public SLList() {
sentinel = new IntNode(63, null);
size = 0;
}
public SLList(int x) {
sentinel = new IntNode(63, null);
sentinel.next = new IntNode(x, null);
size = 1;
}
public void addFirst(int x) {
sentinel.next = new IntNode(x, sentinel.next);
size += 1;
}
public void addLast(int x) {
size += 1;
IntNode p = sentinel;
while (p.next != null) {
p = p.next;
}
p.next = new IntNode(x, null);
}
public int size() {
return size;
}
public Iterator<Integer> iterator() {
return new SLListIterator();
}
private class SLListIterator implements Iterator<Integer> {
private IntNode p;
public SLListIterator() {
p = sentinel.next;
}
public boolean hasNext() {
return p != null;
}
public Integer next() {
int returnItem = p.item;
p = p.next;
return returnItem;
}
}
}
#include <iostream>
template <typename T>
class SLList {
public:
class IntNode {
public:
T item;
IntNode* next;
IntNode(T i, IntNode* n) {
item = i;
next = n;
}
};
private:
IntNode* sentinel;
int size;
public:
SLList() {
sentinel = new IntNode(63, nullptr);
size = 0;
}
explicit SLList(T x) {
sentinel = new IntNode(63, nullptr);
sentinel->next = new IntNode(x, nullptr);
size = 1;
}
void addFirst(T x) {
sentinel->next = new IntNode(x, sentinel->next);
size += 1;
}
void addLast(T x) {
size += 1;
IntNode* p = sentinel;
while (p->next != nullptr) {
p = p->next;
}
p->next = new IntNode(x, nullptr);
}
[[nodiscard]] int size_() const {
return size;
}
class iterator {
private:
IntNode* current;
public:
explicit iterator(IntNode* start) : current(start) {}
T& operator*() { return current->item; }
iterator& operator++() { current = current->next; return *this; }
bool operator!=(const iterator& other) const { return current != other.current; }
};
iterator begin() { return iterator(sentinel->next); }
iterator end() { return iterator(nullptr); }
};
class SLList:
class IntNode:
def __init__(self, i, n):
self.item = i
self.next = n
def __init__(self, x=None):
self.sentinel = self.IntNode(None, None)
self.size = 0
if x is not None: # If x is provided, add it as the first element
self.sentinel.next = self.IntNode(x, None)
self.size = 1
def addFirst(self, x):
self.sentinel.next = self.IntNode(x, self.sentinel.next)
self.size += 1
def addLast(self, x):
p = self.sentinel
while p.next is not None:
p = p.next
p.next = self.IntNode(x, None)
self.size += 1
def __len__(self):
return self.size
def __iter__(self):
p = self.sentinel.next
while p is not None:
yield p.item
p = p.next
2.2 Doubly Linked Lists & Deques
import java.util.LinkedList;
public class DLList {
public static void main(String[] args) {
LinkedList<String> linkedList = new LinkedList<>();
linkedList.add("A");
linkedList.add("B");
linkedList.addLast("C");
linkedList.addFirst("D");
linkedList.add(2, "E");
System.out.println("Linked list : " + linkedList);
}
}
#include <list>
#include <iostream>
int main() {
std::list<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
for(auto i : myList) {
std::cout << i << " ";
}
return 0;
}
from collections import deque
# Initialize a deque
my_deque = deque([1, 2, 3])
# Append to the right
my_deque.append(4)
print("Deque after appending 4:", my_deque) # Output: deque([1, 2, 3, 4])
# Append to the left
my_deque.appendleft(0)
print("Deque after appending 0 to the left:", my_deque) # Output: deque([0, 1, 2, 3, 4])
# Pop from the right
popped_right = my_deque.pop()
print("Popped element from the right:", popped_right) # Output: 4
print("Deque after popping from the right:", my_deque) # Output: deque([0, 1, 2, 3])
# Pop from the left
popped_left = my_deque.popleft()
print("Popped element from the left:", popped_left) # Output: 0
print("Deque after popping from the left:", my_deque) # Output: deque([1, 2, 3])
# Rotate the deque (positive value rotates to the right)
my_deque.rotate(2)
print("Deque after rotating 2 positions to the right:", my_deque) # Output: deque([2, 3, 1])
# Rotate the deque (negative value rotates to the left)
my_deque.rotate(-1)
print("Deque after rotating 1 position to the left:", my_deque) # Output: deque([3, 1, 2])
# You can also use deque as a fixed-size queue with maxlen
limited_deque = deque(maxlen=3)
limited_deque.extend([1, 2, 3, 4]) # Oldest element (1) will be automatically removed
print("Limited deque:", limited_deque) # Output: deque([2, 3, 4], maxlen=3)
import java.util.ArrayList;
public class LinkedList<T> {
private class Node {
public T item;
public Node prev;
public Node next;
public Node(T i, Node p, Node n) {
item = i;
prev = p;
next = n;
}
}
private final Node sentinel;
private int size;
public LinkedList() {
sentinel = new Node(null, null, null);
sentinel.prev = sentinel;
sentinel.next = sentinel;
size = 0;
}
public void addFirst(T x) {
Node newNode = new Node(x, sentinel, sentinel.next);
sentinel.next.prev = newNode;
sentinel.next = newNode;
size++;
}
public void addLast(T x) {
Node newNode = new Node(x, sentinel.prev, sentinel);
sentinel.prev.next = newNode;
sentinel.prev = newNode;
size++;
}
public ArrayList<T> toList() {
ArrayList<T> returnList = new ArrayList<>();
Node p = sentinel.next;
while (p != sentinel) {
returnList.add(p.item);
p = p.next;
}
return returnList;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public T removeFirst() {
if (isEmpty()) {
return null;
}
Node first = sentinel.next;
sentinel.next = first.next;
first.next.prev = sentinel;
size--;
return first.item;
}
public T removeLast() {
if (isEmpty()) {
return null;
}
Node last = sentinel.prev;
sentinel.prev = last.prev;
last.prev.next = sentinel;
size--;
return last.item;
}
public T get(int index) {
if (index < 0 || index >= size) {
return null;
}
Node p = sentinel.next;
for (int i = 0; i < index; i++) {
p = p.next;
}
return p.item;
}
public T getRecursive(int index) {
if (index < 0 || index >= size) {
return null;
}
return getRecursiveHelper(sentinel.next, index);
}
private T getRecursiveHelper(Node p, int index) {
if (index == 0) {
return p.item;
}
return getRecursiveHelper(p.next, index - 1);
}
}
#include <vector>
template <typename T>
class LinkedList {
private:
struct Node {
T item;
Node* prev;
Node* next;
Node(T i, Node* p, Node* n) : item(i), prev(p), next(n) {}
};
Node* sentinel;
int size;
public:
LinkedList() : size(0) {
sentinel = new Node(T(), nullptr, nullptr);
sentinel->prev = sentinel;
sentinel->next = sentinel;
}
~LinkedList() {
Node* current = sentinel->next;
while (current != sentinel) {
Node* next = current->next;
delete current;
current = next;
}
delete sentinel;
}
void addFirst(T x) {
Node* newNode = new Node(x, sentinel, sentinel->next);
sentinel->next->prev = newNode;
sentinel->next = newNode;
size++;
}
void addLast(T x) {
Node* newNode = new Node(x, sentinel->prev, sentinel);
sentinel->prev->next = newNode;
sentinel->prev = newNode;
size++;
}
std::vector<T> toList() {
std::vector<T> returnList;
Node* p = sentinel->next;
while (p != sentinel) {
returnList.push_back(p->item);
p = p->next;
}
return returnList;
}
[[nodiscard]] bool isEmpty() const {
return size == 0;
}
[[nodiscard]] int size_() const {
return size;
}
T removeFirst() {
if (isEmpty()) {
return T();
}
Node* first = sentinel->next;
sentinel->next = first->next;
first->next->prev = sentinel;
size--;
T item = first->item;
delete first;
return item;
}
T removeLast() {
if (isEmpty()) {
return T();
}
Node* last = sentinel->prev;
sentinel->prev = last->prev;
last->prev->next = sentinel;
size--;
T item = last->item;
delete last;
return item;
}
T get(const int index) {
if (index < 0 || index >= size) {
return T();
}
Node* p = sentinel->next;
for (int i = 0; i < index; i++) {
p = p->next;
}
return p->item;
}
T getRecursive(const int index) {
if (index < 0 || index >= size) {
return T();
}
return getRecursiveHelper(sentinel->next, index);
}
private:
T getRecursiveHelper(Node* p, const int index) {
if (index == 0) {
return p->item;
}
return getRecursiveHelper(p->next, index - 1);
}
};
class Node:
def __init__(self, item, prev, next):
self.item = item
self.prev = prev
self.next = next
class LinkedList:
def __init__(self):
self.sentinel = Node(None, None, None)
self.sentinel.prev = self.sentinel
self.sentinel.next = self.sentinel
self.size = 0
def addFirst(self, x):
newNode = Node(x, self.sentinel, self.sentinel.next)
self.sentinel.next.prev = newNode
self.sentinel.next = newNode
self.size += 1
def addLast(self, x):
newNode = Node(x, self.sentinel.prev, self.sentinel)
self.sentinel.prev.next = newNode
self.sentinel.prev = newNode
self.size += 1
def toList(self):
returnList = []
p = self.sentinel.next
while p != self.sentinel:
returnList.append(p.item)
p = p.next
return returnList
def isEmpty(self):
return self.size == 0
def size_(self):
return self.size
def removeFirst(self):
if self.isEmpty():
return None
first = self.sentinel.next
self.sentinel.next = first.next
first.next.prev = self.sentinel
self.size -= 1
return first.item
def removeLast(self):
if self.isEmpty():
return None
last = self.sentinel.prev
self.sentinel.prev = last.prev
last.prev.next = self.sentinel
self.size -= 1
return last.item
def get(self, index):
if index < 0 or index >= self.size:
return None
p = self.sentinel.next
for i in range(index):
p = p.next
return p.item
def getRecursive(self, index):
if index < 0 or index >= self.size:
return None
return self._getRecursiveHelper(self.sentinel.next, index)
def _getRecursiveHelper(self, p, index):
if index == 0:
return p.item
return self._getRecursiveHelper(p.next, index - 1)
import java.util.List;
import java.util.ArrayList;
import java.lang.Math;
public class ArrayDeque<T> {
private T[] items;
private int size;
private int nextFirst;
private int nextLast;
public ArrayDeque() {
items = (T[]) new Object[8];
size = 0;
nextFirst = 0;
nextLast = 1;
}
public void addFirst(T x) {
checkAndResize();
items[nextFirst] = x;
nextFirst = Math.floorMod(nextFirst - 1, items.length);
size += 1;
}
public void addLast(T x) {
checkAndResize();
items[nextLast] = x;
nextLast = Math.floorMod(nextLast + 1, items.length);
size += 1;
}
public List<T> toList() {
List<T> list = new ArrayList<>();
for (int i = 0; i < size; i++) {
list.add(get(i));
}
return list;
}
public boolean isEmpty() {
return size == 0;
}
public int size() {
return size;
}
public T removeFirst() {
if (isEmpty()) {
return null;
}
nextFirst = Math.floorMod(nextFirst + 1, items.length);
T item = items[nextFirst];
items[nextFirst] = null;
size -= 1;
checkAndResize();
return item;
}
public T removeLast() {
if (isEmpty()) {
return null;
}
nextLast = Math.floorMod(nextLast - 1, items.length);
T item = items[nextLast];
items[nextLast] = null;
size -= 1;
checkAndResize();
return item;
}
private void resize(int capacity) {
T[] a = (T[]) new Object[capacity];
for (int i = 0; i < size; i++) {
a[i] = get(i);
}
items = a;
nextFirst = capacity - 1;
nextLast = size;
}
private void checkAndResize() {
if (size == items.length) {
resize(size * 2);
} else if (items.length >= 16 && size < items.length / 4) {
resize(items.length / 2);
}
}
public T get(int index) {
if (index >= size || index < 0) {
return null;
}
return items[Math.floorMod(nextFirst + 1 + index, items.length)];
}
public T getRecursive(int index) {
throw new UnsupportedOperationException("No need to implement getRecursive for proj 1b");
}
}
#include <vector>
template <typename T>
class ArrayDeque {
private:
T* items;
int size;
int nextFirst;
int nextLast;
int capacity;
void resize(const int newCapacity) {
T* a = new T[newCapacity];
for (int i = 0; i < size; i++) {
a[i] = get(i);
}
delete[] items;
items = a;
capacity = newCapacity;
nextFirst = capacity - 1;
nextLast = size;
}
void checkAndResize() {
if (size == capacity) {
resize(capacity * 2);
} else if (capacity >= 16 && size < capacity / 4) {
resize(capacity / 2);
}
}
public:
ArrayDeque(): size(0), nextFirst(0), nextLast(1), capacity(8) {
items = new T[capacity];
}
~ArrayDeque() {
delete[] items;
}
void addFirst(T x) {
checkAndResize();
items[nextFirst] = x;
nextFirst = (nextFirst - 1 + capacity) % capacity;
size += 1;
}
void addLast(T x) {
checkAndResize();
items[nextLast] = x;
nextLast = (nextLast + 1) % capacity;
size += 1;
}
std::vector<T> toList() {
std::vector<T> list;
for (int i = 0; i < size; i++) {
list.push_back(get(i));
}
return list;
}
[[nodiscard]] bool isEmpty() const {
return size == 0;
}
[[nodiscard]] int size_() const {
return size;
}
T removeFirst() {
if (isEmpty()) {
return T();
}
nextFirst = (nextFirst + 1) % capacity;
T item = items[nextFirst];
size -= 1;
checkAndResize();
return item;
}
T removeLast() {
if (isEmpty()) {
return T();
}
nextLast = (nextLast - 1 + capacity) % capacity;
T item = items[nextLast];
size -= 1;
checkAndResize();
return item;
}
T get(const int index) {
if (index >= size || index < 0) {
return T();
}
return items[(nextFirst + 1 + index) % capacity];
}
};
class ArrayDeque:
def __init__(self):
self.capacity = 8
self.items = [None] * self.capacity
self.size = 0
self.nextFirst = 0
self.nextLast = 1
def addFirst(self, x):
self.checkAndResize()
self.items[self.nextFirst] = x
self.nextFirst = (self.nextFirst - 1 + self.capacity) % self.capacity
self.size += 1
def addLast(self, x):
self.checkAndResize()
self.items[self.nextLast] = x
self.nextLast = (self.nextLast + 1) % self.capacity
self.size += 1
def toList(self):
return [self.get(i) for i in range(self.size)]
def isEmpty(self):
return self.size == 0
def size_(self):
return self.size
def removeFirst(self):
if self.isEmpty():
return None
self.nextFirst = (self.nextFirst + 1) % self.capacity
item = self.items[self.nextFirst]
self.items[self.nextFirst] = None
self.size -= 1
self.checkAndResize()
return item
def removeLast(self):
if self.isEmpty():
return None
self.nextLast = (self.nextLast - 1 + self.capacity) % self.capacity
item = self.items[self.nextLast]
self.items[self.nextLast] = None
self.size -= 1
self.checkAndResize()
return item
def resize(self, newCapacity):
a = [None] * newCapacity
for i in range(self.size):
self.get(i)
self.items = a
self.capacity = newCapacity
self.nextFirst = newCapacity - 1
self.nextLast = self.size
def checkAndResize(self):
if self.size == self.capacity:
self.resize(self.capacity * 2)
elif self.capacity >= 16 and self.size < self.capacity // 4:
self.resize(self.capacity // 2)
def get(self, index):
if index >= self.size or index < 0:
return None
return self.items[(self.nextFirst + 1 + index) % self.capacity]
3 Union-Find
3.1 Quick Find (Eager Approach)
parent[i]is the root of, and are connected if and only if they have the same parent[i].Find: Check if
and have the same parent[i].Union: To merge components containing
and , change all entries whose id equals parent[p]toparent[q].
3.2 Quick Union (Lazy Approach)
parent[i] is the parent of
, root of is parent[parent[...[i]]] (keep going until it doesn't change). Find: Check if
and have the same root. Union: To merge components containing
and , set the parent of 's root to the parent of 's root.
3.3 Quick Union Improvements
Two Improvements: Weighting and Path Compression (WQUPC).
Weighted quick-union
Modify quick-union to avoid tall trees.
Keep track of size of each tree (number of objects).
Balance by linking root of smaller tree to root of larger tree.
Path compression
Just after computing the root of
, set the parent of each examined node to point to that root.
rank[i]is the size of the tree rooted at. Property: Starting from an empty data structure, any sequence of
union-find operations on objects makes array accesses. In theory, WQUPC is not linear; in practice, it is.
Application: Percoloation, games, dynamic connectivity, least common ancestor, Kruskal's minimum spanning tree algorithm, etc.
public class UnionFind {
private final int[] parent;
private final byte[] rank;
private int count;
public UnionFind(int n) {
if (n < 0) throw new IllegalArgumentException();
count = n;
parent = new int[n];
rank = new byte[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
public int find(int p) {
validate(p);
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
return p;
}
public int count() {
return count;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public void union(int p, int q) {
int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] < rank[rootQ]) parent[rootP] = rootQ;
else if (rank[rootP] > rank[rootQ]) parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
private void validate(int p) {
int n = parent.length;
if (p < 0 || p >= n) {
throw new IllegalArgumentException("index " + p + " is not between 0 and " + (n - 1));
}
}
}
#ifndef UNIONFIND_H
#define UNIONFIND_H
#include <vector>
class UnionFind {
private:
std::vector<int> parent;
std::vector<int> rank;
int count;
public:
explicit UnionFind(int n);
int find(int p);
[[nodiscard]] int countComponents() const;
bool connected(int p, int q);
void unionSets(int p, int q);
private:
void validate(int p) const;
};
#endif // UNIONFIND_H
#include <stdexcept>
#include <string>
#include "UnionFind.h"
UnionFind::UnionFind(const int n) {
if (n < 0) throw std::invalid_argument("n must be non-negative");
count = n;
parent.resize(n);
rank.resize(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int UnionFind::find(int p) {
validate(p);
while (p != parent[p]) {
parent[p] = parent[parent[p]]; // Path compression
p = parent[p];
}
return p;
}
int UnionFind::countComponents() const {
return count;
}
bool UnionFind::connected(int p, int q) {
return find(p) == find(q);
}
void UnionFind::unionSets(int p, int q) {
const int rootP = find(p);
int rootQ = find(q);
if (rootP == rootQ) return;
if (rank[rootP] < rank[rootQ]) {
parent[rootP] = rootQ;
} else if (rank[rootP] > rank[rootQ]) {
parent[rootQ] = rootP;
} else {
parent[rootQ] = rootP;
rank[rootP]++;
}
count--;
}
void UnionFind::validate(const int p) const {
int n = static_cast<int>(parent.size());
if (p < 0 || p >= n) {
throw std::invalid_argument("index " + std::to_string(p) + " is not between 0 and " +
std::to_string(n - 1));
}
}
class UnionFind:
def __init__(self, n):
if n < 0:
raise ValueError("n must be non-negative")
self.count = n
self.parent = list(range(n))
self.rank = [0] * n
def find(self, p):
self.validate(p)
while p != self.parent[p]:
self.parent[p] = self.parent[self.parent[p]]
p = self.parent[p]
return p
def count_components(self):
return self.count
def connected(self, p, q):
return self.find(p) == self.find(q)
def union(self, p, q):
root_p = self.find(p)
root_q = self.find(q)
if root_p == root_q:
return
if self.rank[root_p] < self.rank[root_q]:
self.parent[root_p] = root_q
elif self.rank[root_p] > self.rank[root_q]:
self.parent[root_q] = root_p
else:
self.parent[root_q] = root_p
self.rank[root_p] += 1
self.count -= 1
def validate(self, p):
n = len(self.parent)
if p < 0 or p >= n:
raise ValueError(f"index {p} is not between 0 and {n - 1}")
4 Bags, Queues and Stacks
Stack: Examine the item most recently added (LIFO: last in first out).
Queue: Examine the item least recently added (FIFO: first in first out).
4.1 Stacks
Defintions
Client: program using operations defined in interface.
Implementation: actual code implementing operations.
Interface: description of data types, basic operations.
Separate interface from implementation!
Benefits:
Clients can't know details of implementation => client has many implementation from which to choose.
Implementation can't know details of client needs => many clients can re-use the same implementation.
Design: creates modular, reusable libraries.
Performance: use optimized implementation where it matters.
4.1.1 Built-In Stacks
import java.util.Stack;
public class StackExample {
public static void main(String[] args) {
Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
stack.push(3);
System.out.println(stack.pop()); // Outputs 3
System.out.println(stack.pop()); // Outputs 2
System.out.println(stack.peek()); // Outputs 1
System.out.println(stack.empty());
}
}
#include <iostream>
#include <stack>
int main() {
std::stack<int> stack;
// Push elements to the stack
stack.push(1);
stack.push(2);
stack.push(3);
std::cout << stack.top() << std::endl;
stack.pop();
std::cout << stack.top() << std::endl;
stack.pop();
std::cout << stack.top() << std::endl;
std::cout << (stack.empty() ? "true" : "false") << std::endl;
return 0;
}
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
print(stack.pop())
print(stack.pop())
print(stack[-1])
print(len(stack) == 0)
4.1.2 Linked-List Implementation
Stack pop
Save item to return.
Delete first node.
Return saved item.
Stack push
Save a link to the list.
Create a new node for the beginning.
Set the instance variables in the new node.
Properties
Every operation takes constant time in the worst case.
A stack with
items uses bytes.
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedStack<Item> implements Iterable<Item> {
private int n;
private Node first;
private class Node {
private Item item;
private Node next;
}
public LinkedStack() {
first = null;
n = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return n;
}
public void push(Item item) {
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
n++;
}
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = first.item;
first = first.next;
n--;
return item;
}
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return first.item;
}
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item).append(" ");
return s.toString();
}
public Iterator<Item> iterator() {
return new LinkedIterator();
}
private class LinkedIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}
#include <iostream>
#include <stdexcept>
template <typename Item>
class LinkedStack {
private:
struct Node {
Item item;
Node* next;
};
int n;
Node* first;
public:
LinkedStack() : n(0), first(nullptr) {}
[[nodiscard]] bool isEmpty() const {
return first == nullptr;
}
[[nodiscard]] int size() const {
return n;
}
void push(const Item& item) {
Node* oldfirst = first;
first = new Node();
first->item = item;
first->next = oldfirst;
n++;
}
Item pop() {
if (isEmpty()) throw std::runtime_error("Stack underflow");
Item item = first->item;
const Node* oldfirst = first;
first = first->next;
delete oldfirst;
n--;
return item;
}
[[nodiscard]] Item peek() const {
if (isEmpty()) throw std::runtime_error("Stack underflow");
return first->item;
}
class Iterator {
private:
Node* current;
public:
explicit Iterator(Node* start) : current(start) {}
bool operator!=(const Iterator& other) const {
return current != other.current;
}
Iterator& operator++() {
current = current->next;
return *this;
}
Item& operator*() {
return current->item;
}
};
[[nodiscard]] Iterator begin() const {
return Iterator(first);
}
[[nodiscard]] Iterator end() const {
return Iterator(nullptr);
}
};
class Node:
def __init__(self, item):
self.item = item
self.next = None
class LinkedStack:
def __init__(self):
self.first = None
self.n = 0
def is_empty(self):
return self.first is None
def size(self):
return self.n
def push(self, item):
oldfirst = self.first
self.first = Node(item)
self.first.next = oldfirst
self.n += 1
def pop(self):
if self.is_empty():
raise Exception("Stack underflow")
item = self.first.item
self.first = self.first.next
self.n -= 1
return item
def peek(self):
if self.is_empty():
raise Exception("Stack underflow")
return self.first.item
def __iter__(self):
current = self.first
while current:
yield current.item
current = current.next
4.1.3 Resizing-Array Implementation
Property: Uses between
when full. when one-quarter full.
Linked-List Implementation | Resizing-Array Implementation |
|---|---|
Every operation takes constant time in the worst case. | Every operation takes constant amortized time. |
Uses extra time and space to deal with the links. | Less wasted space. |
import java.util.Iterator;
import java.util.NoSuchElementException;
public class ResizingArrayStack<Item> implements Iterable<Item> {
private static final int INIT_CAPACITY = 8;
private Item[] a;
private int n;
public ResizingArrayStack() {
a = (Item[]) new Object[INIT_CAPACITY];
n = 0;
}
public boolean isEmpty() {
return n == 0;
}
public int size() {
return n;
}
private void resize(int capacity) {
assert capacity >= n;
a = java.util.Arrays.copyOf(a, capacity);
// textbook implementation
// Item[] copy = (Item[]) new Object[capacity];
// for (int i = 0; i < n; i++) {
// copy[i] = a[i];
// }
// a = copy;
}
public void push(Item item) {
if (n == a.length) resize(2 * a.length); // double size of array if necessary
a[n++] = item; // add item
}
public Item pop() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
Item item = a[n-1];
a[n-1] = null; // to avoid loitering
n--;
// shrink size of array if necessary
if (n > 0 && n == a.length/4) resize(a.length/2);
return item;
}
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Stack underflow");
return a[n-1];
}
public Iterator<Item> iterator() {
return new ReverseArrayIterator();
}
private class ReverseArrayIterator implements Iterator<Item> {
private int i;
public ReverseArrayIterator() {
i = n-1;
}
public boolean hasNext() {
return i >= 0;
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
return a[i--];
}
}
}
// no iterator for C++
#include <iostream>
#include <vector>
#include <stdexcept>
template <typename Item>
class ResizingArrayStack {
private:
static constexpr int INIT_CAPACITY = 8;
std::vector<Item> a;
int n;
public:
ResizingArrayStack() : a(INIT_CAPACITY), n(0) {}
[[nodiscard]] bool isEmpty() const {
return n == 0;
}
[[nodiscard]] int size() const {
return n;
}
void push(const Item& item) {
if (n == a.size()) resize(2 * a.size());
a[n++] = item;
}
Item pop() {
if (isEmpty()) throw std::runtime_error("Stack underflow");
Item item = a[n - 1];
a[n - 1] = Item();
n--;
if (n > 0 && n == a.size() / 4) resize(a.size() / 2);
return item;
}
[[nodiscard]] Item peek() const {
if (isEmpty()) throw std::runtime_error("Stack underflow");
return a[n - 1];
}
private:
void resize(int capacity) {
a.resize(capacity);
}
};
# Python lists handle resizing automatically
class ResizingArrayStack:
def __init__(self):
self._a = []
self._n = 0
def is_empty(self):
return self._n == 0
def size(self):
return self._n
def push(self, item):
if self._n == len(self._a):
self._resize(2 * len(self._a))
self._a.append(item) # Python lists handle resizing automatically
self._n += 1
def pop(self):
if self.is_empty():
raise Exception("Stack underflow")
self._n -= 1
item = self._a.pop()
if self._n > 0 and self._n == len(self._a) // 4:
self._resize(len(self._a) // 2)
return item
def peek(self):
if self.is_empty():
raise Exception("Stack underflow")
return self._a[-1]
4.2 Queues
4.2.1 Built-in Queues
import java.util.LinkedList;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue.poll()); // Outputs 1
System.out.println(queue.peek()); // Outputs 2
System.out.println(queue.isEmpty()); // Outputs false
}
}
#include <iostream>
#include <queue>
int main() {
std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);
std::cout << q.front() << std::endl;
q.pop();
std::cout << (q.empty() ? "true" : "false") << std::endl;
return 0;
}
import queue
q = queue.Queue()
q.put(1)
q.put(2)
q.put(3)
print(q.get())
print(q.empty())
4.2.2 Queue Implementation
Queue dequeue
Save item to return.
Delete first node.
Return saved item.
Queue enqueue
Save a link to the last node.
Create a new node for the end.
Link the new node to the end of the list.
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedQueue<Item> implements Iterable<Item> {
private int n;
private Node first;
private Node last;
private class Node {
private Item item;
private Node next;
}
public LinkedQueue() {
first = null;
last = null;
n = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return n;
}
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return first.item;
}
public void enqueue(Item item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) first = last;
else oldlast.next = last;
n++;
}
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Item item = first.item;
first = first.next;
n--;
if (isEmpty()) last = null;
return item;
}
public String toString() {
StringBuilder s = new StringBuilder();
for (Item item : this)
s.append(item).append(" ");
return s.toString();
}
public Iterator<Item> iterator() {
return new LinkedIterator();
}
private class LinkedIterator implements Iterator<Item> {
private Node current = first;
public boolean hasNext() {
return current != null;
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}
#include <iostream>
#include <stdexcept>
template <typename Item>
class LinkedQueue {
private:
struct Node {
Item item;
Node* next;
};
int n;
Node* first;
Node* last;
public:
LinkedQueue() : n(0), first(nullptr), last(nullptr) {}
[[nodiscard]] bool isEmpty() const {
return first == nullptr;
}
[[nodiscard]] int size() const {
return n;
}
[[nodiscard]] Item peek() const {
if (isEmpty()) throw std::runtime_error("Queue underflow");
return first->item;
}
void enqueue(const Item& item) {
Node* oldlast = last;
last = new Node;
last->item = item;
last->next = nullptr;
if (isEmpty()) first = last;
else oldlast->next = last;
n++;
}
Item dequeue() {
if (isEmpty()) throw std::runtime_error("Queue underflow");
Item item = first->item;
const Node* oldfirst = first;
first = first->next;
delete oldfirst;
n--;
if (isEmpty()) last = nullptr;
return item;
}
friend std::ostream& operator<<(std::ostream& os, const LinkedQueue<Item>&
queue) {
for (Node* current = queue.first; current != nullptr; current = current->next) {
os << current->item << " ";
}
return os;
}
class Iterator {
private:
Node* current;
public:
explicit Iterator(Node* start) : current(start) {}
[[nodiscard]] bool hasNext() const {
return current != nullptr;
}
Item next() {
if (!hasNext()) throw std::runtime_error("No more elements");
Item item = current->item;
current = current->next;
return item;
}
[[nodiscard]] Node* getCurrent() const {
return current;
}
Iterator& operator++() {
if (current) {
current = current->next;
}
return *this;
}
Item& operator*() {
if (!current) {
throw std::runtime_error("Dereferencing invalid iterator");
}
return current->item;
}
};
friend bool operator!=(const Iterator& lhs, const Iterator& rhs) {
return lhs.getCurrent() != rhs.getCurrent();
}
[[nodiscard]] Iterator begin() const {
return Iterator(first);
}
[[nodiscard]] Iterator end() const {
return Iterator(nullptr);
}
};
class Node:
def __init__(self, item):
self.item = item
self.next = None
class LinkedQueue:
def __init__(self):
self.n = 0
self.first = None
self.last = None
def is_empty(self):
return self.first is None
def size(self):
return self.n
def peek(self):
if self.is_empty():
raise Exception("Queue underflow")
return self.first.item
def enqueue(self, item):
oldlast = self.last
self.last = Node(item)
if self.is_empty():
self.first = self.last
else:
oldlast.next = self.last
self.n += 1
def dequeue(self):
if self.is_empty():
raise Exception("Queue underflow")
item = self.first.item
self.first = self.first.next
self.n -= 1
if self.is_empty():
self.last = None
return item
def __iter__(self):
current = self.first
while current:
yield current.item
current = current.next
def __str__(self):
return " ".join(str(item) for item in self)
4.3 Generics
Use generics for different types of objects!
The implementation above has already taken generics into account.
4.4 Iterators
Iterators allow clients to iterate through the items in a collection.
Using iterator, we can:
for (Item item : collection) {
// do something with item
}
The implementation above has already taken iterators into account.
For more information on iterators, please visit Iterators in C++.
4.5 Bag (Princeton)
The order of items in a bag does not matter.
import java.util.Iterator;
import java.util.NoSuchElementException;
public class Bag<Item> implements Iterable<Item> {
private Node<Item> first;
private int n;
private static class Node<Item> {
private Item item;
private Node<Item> next;
}
public Bag() {
first = null;
n = 0;
}
public boolean isEmpty() {
return first == null;
}
public int size() {
return n;
}
public void add(Item item) {
Node<Item> oldfirst = first;
first = new Node<Item>();
first.item = item;
first.next = oldfirst;
n++;
}
public Iterator<Item> iterator() {
return new LinkedIterator(first);
}
private class LinkedIterator implements Iterator<Item> {
private Node<Item> current;
public LinkedIterator(Node<Item> first) {
current = first;
}
public boolean hasNext() {
return current != null;
}
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = current.item;
current = current.next;
return item;
}
}
}
5 Elementary Sorts
5.1 Selection Sort
Time Complexity:
. Space Complexity:
.
Selection Sort
In iteration
, find index of smallest remaining entry. Swap
a[i]anda[min].
Properties
Use
compares and exchanges. Quadratic time, even if the input is sorted!
Data movement is minimal: linear number of exchanges -> suitable for small number of data.
public class Selection {
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 0; i < n; i++) {
int min = i;
for (int j = i + 1; j < n; j++) {
if (less(a[j], a[min])) {
min = j;
}
}
exch(a, i, min);
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
#include <algorithm>
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
std::swap(arr[minIndex], arr[i]);
}
}
def selection_sort(arr):
for i in range(len(arr)):
min_index = i
for j in range(i+1, len(arr)):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
5.2 Insertion Sort
Time Complexity:
. Space Complexity:
.
Insertion Sort
In iteration
, swap with each larger entry to its left. Entries to the left of
are in ascending order.
Definitions
Inversion: A pair of keys that are out of order.
Example A E E L M O T R X P S
Six inversions: T-R T-P T-S R-P X-P X-S
Partially Sorted: An array is partially sorted if the number of inversions is
.
Property: For partially-sorted arrays, insertion sort runs in linear time.
Proof: Number of exchanges equals the number of inversions (number of compares = exchanges + (N – 1)).
Running Time Analysis
On average: To sort a randomly-ordered array with distinct keys, insertion sort uses
compares and exchanges on average. Best case: If the array is in ascending order, insertion sort makes
compares and exchanges. Worst Case: If the array is in descending order (and no duplicates), insertion sort makes
compares and exchanges.
public class Insertion {
public static void sort(Comparable[] a) {
int n = a.length;
for (int i = 1; i < n; i++) {
for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
exch(a, j, j - 1);
}
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
#include <algorithm>
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
5.3 Shell Sort
Shell Sort
Move entries more than one position at a time by
-sorting the array. -sort the array: Insertion sort, with stride .
Increment Sequence
Knuth's increment sequence (3x+1): 1, 4, 13, 40, 121, 364, 1093, ... (OK, easy to compute)
Sedgewick's increment sequence: ( merging of
and 1, 5, 19, 41, 109, 209, 505, 929, 2161, ... (Good, tough to beat empirical studies).
Property: With the
public class Shell {
public static void sort(Comparable[] a) {
int n = a.length;
int h = 1;
while (h < n / 3) {
h = 3 * h + 1;
}
while (h >= 1) {
for (int i = h; i < n; i++) {
for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
exch(a, j, j - h);
}
}
h = h / 3;
}
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
private static void exch(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
#include <vector>
void shellSortKnuth(std::vector<int>& arr) {
int n = arr.size();
int gap = 1;
while (gap < n/3) {
gap = 3 * gap + 1;
}
while (gap >= 1) {
for (int i = gap; i < n; i += 1) {
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
gap /= 3;
}
}
def shell_sort_knuth(arr):
n = len(arr)
gap = 1
while gap < n//3:
gap = 3 * gap + 1
while gap >= 1:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 3
5.4 Shuffling
Knuth Shuffle
In iteration
, pick integer between and uniformly at random. Swap
a[i]anda[r].
import java.util.Random;
public class KnuthShuffle {
public static void shuffle(int[] array) {
int n = array.length;
Random random = new Random();
for (int i = 0; i < n; i++) {
int r = i + random.nextInt(n - i);
int temp = array[i];
array[i] = array[r];
array[r] = temp;
}
}
}
#include <random>
#include <algorithm>
void knuthShuffle(int array[], int n) {
// std::random_device is a C++ class that generates truly random numbers.
std::random_device rd;
// std::mt19937 is a Mersenne Twister pseudo-random generator of 32-bit numbers.
// However, it's not truly random and needs to be seeded to ensure different outputs for
different program runs.
// That's where std::random_device comes in.
std::mt19937 gen(rd());
// std::uniform_int_distribution<> is a template class in C++ that produces random
integers in a specified range.
for(int i = 0; i < n; i++) {
std::uniform_int_distribution<> dis(i, n - 1);
int r = dis(gen);
std::swap(array[i], array[r]);
}
}
import random
def knuth_shuffle(array):
n = len(array)
for i in range(n):
r = i + random.randint(0, n - i - 1)
array[i], array[r] = array[r], array[i]
5.5 Convex Hull
Convex Hull: A convex hull of a set of
Equivalent definitions
Smallest convex set containing all the points.
Smallest area convex polygon enclosing the points.
Convex polygon enclosing the points, whose vertices are points in set.
Geometric properties
Can traverse the convex hull by making only counterclockwise turns.
The vertices of convex hull appear in increasing order of polar angle with respect to point
with lowest -coordinate.
Graham Scan
Choose point
with smallest -coordinate. Sort points by polar angle with
. Consider points in order; discard unless it create a ccw (counterclockwise) turn.
Implementing ccw: Given three points
ccw
Determinant (or cross product) gives
signed area of planar triangle. If signed area
, then -> -> is counterclockwise. If signed area
, then -> -> is clockwise. If signed area
, then -> -> are collinear.
Proof
Applications
Hammer nails perpendicular to plane, stretch elastic rubber band around points
Find shortest path in the plane from
to that avoids a polygonal obstacle. Shortest path is either straight line from
to or it is one of two polygonal chains of convex hull . 
Given
points in the plane, find a pair of points with the largest Euclidean distance between them. Farthest pair of points are extreme points on convex hull.
Cost of Convex Hull:
Proof: Convex hull reduces to sorting
cost of sorting cost of reduction
Point2D
import java.util.Comparator;
public record Point2D(double x, double y) implements Comparable<Point2D> {
public double distanceTo(Point2D that) {
double dx = this.x - that.x;
double dy = this.y - that.y;
return Math.sqrt(dx * dx + dy * dy);
}
public double distanceSquaredTo(Point2D that) {
double dx = this.x - that.x;
double dy = this.y - that.y;
return dx * dx + dy * dy;
}
public int compareTo(Point2D that) {
if (this.y < that.y) return -1;
if (this.y > that.y) return +1;
return Double.compare(this.x, that.x);
}
public Comparator<Point2D> polarOrder() {
return new PolarOrder();
}
private class PolarOrder implements Comparator<Point2D> {
public int compare(Point2D q1, Point2D q2) {
double dx1 = q1.x - x;
double dy1 = q1.y - y;
double dx2 = q2.x - x;
double dy2 = q2.y - y;
if (dy1 >= 0 && dy2 < 0) return -1;
else if (dy2 >= 0 && dy1 < 0) return +1;
else if (dy1 == 0 && dy2 == 0) {
if (dx1 >= 0 && dx2 < 0) return -1;
else if (dx2 >= 0 && dx1 < 0) return +1;
else return 0;
} else return -ccw(Point2D.this, q1, q2);
}
}
public static int ccw(Point2D a, Point2D b, Point2D c) {
double area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (area2 < 0) return -1;
else if (area2 > 0) return +1;
else return 0;
}
public boolean equals(Object other) {
if (other == this) return true;
if (other == null) return false;
if (other.getClass() != this.getClass()) return false;
Point2D that = (Point2D) other;
return this.x == that.x && this.y == that.y;
}
public String toString() {
return "(" + x + ", " + y + ")";
}
}
#ifndef POINT2D_H #define POINT2D_H #include <iostream> class Point2D { public: double x; double y; Point2D(const double x, const double y) : x(x), y(y) {} [[nodiscard]] double distanceTo(const Point2D& that) const; [[nodiscard]] double distanceSquaredTo(const Point2D& that) const; [[nodiscard]] int compareTo(const Point2D& that) const; struct PolarOrder; bool operator==(const Point2D& other) const; friend std::ostream& operator<<(std::ostream& os, const Point2D& p); static int ccw(const Point2D& a, const Point2D& b, const Point2D& c); }; struct Point2D::PolarOrder { Point2D origin; explicit PolarOrder(const Point2D& origin) : origin(origin) {} bool operator()(const Point2D& q1, const Point2D& q2) const; }; #endif // POINT2D_H
#include <cmath>
#include "Point2D.h"
double Point2D::distanceTo(const Point2D& that) const {
const double dx = this->x - that.x;
const double dy = this->y - that.y;
return std::sqrt(dx * dx + dy * dy);
}
double Point2D::distanceSquaredTo(const Point2D& that) const {
const double dx = this->x - that.x;
const double dy = this->y - that.y;
return dx * dx + dy * dy;
}
int Point2D::compareTo(const Point2D& that) const {
if (this->y < that.y) return -1;
if (this->y > that.y) return +1;
return (this->x < that.x) ? -1 : (this->x > that.x) ? 1 : 0;
}
bool Point2D::PolarOrder::operator()(const Point2D& q1, const Point2D& q2) const {
const double dx1 = q1.x - origin.x;
const double dy1 = q1.y - origin.y;
const double dx2 = q2.x - origin.x;
const double dy2 = q2.y - origin.y;
if (dy1 >= 0 && dy2 < 0) return true;
if (dy2 >= 0 && dy1 < 0) return false;
if (dy1 == 0 && dy2 == 0) {
if (dx1 >= 0 && dx2 < 0) return true;
if (dx2 >= 0 && dx1 < 0) return false;
return false;
}
return ccw(origin, q1, q2) > 0;
}
bool Point2D::operator==(const Point2D& other) const {
return this->x == other.x && this->y == other.y;
}
std::ostream& operator<<(std::ostream& os, const Point2D& p) {
os << "(" << p.x << ", " << p.y << ")";
return os;
}
int Point2D::ccw(const Point2D& a, const Point2D& b, const Point2D& c) {
double area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
if (area2 < 0) return -1;
else if (area2 > 0) return +1;
else return 0;
}
import math
class Point2D:
def __init__(self, x, y):
self.x = x
self.y = y
def distance_to(self, that):
dx = self.x - that.x
dy = self.y - that.y
return math.sqrt(dx * dx + dy * dy)
def distance_squared_to(self, that):
dx = self.x - that.x
dy = self.y - that.y
return dx * dx + dy * dy
def __lt__(self, that):
if self.y < that.y:
return True
if self.y > that.y:
return False
return self.x < that.x
def __eq__(self, other):
if other == self:
return True
if other is None:
return False
if type(other) != type(self):
return False
return self.x == other.x and self.y == other.y
def __str__(self):
return "(" + str(self.x) + ", " + str(self.y) + ")"
@staticmethod
def ccw(a, b, c):
area2 = (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x)
if area2 < 0:
return -1
elif area2 > 0:
return +1
else:
return 0
Graham Scan
import java.util.Arrays;
import java.util.Stack;
public class GrahamScan {
private final Stack<Point2D> hull = new Stack<Point2D>();
public GrahamScan(Point2D[] points) {
if (points == null) throw new IllegalArgumentException("argument is null");
if (points.length == 0) throw new IllegalArgumentException("array is of length 0");
int n = points.length;
Point2D[] a = new Point2D[n];
for (int i = 0; i < n; i++) {
if (points[i] == null)
throw new IllegalArgumentException("points[" + i + "] is null");
a[i] = points[i];
}
Arrays.sort(a);
Arrays.sort(a, 1, n, a[0].polarOrder());
hull.push(a[0]);
int k1;
for (k1 = 1; k1 < n; k1++)
if (!a[0].equals(a[k1])) break;
if (k1 == n) return;
int k2;
for (k2 = k1 + 1; k2 < n; k2++)
if (Point2D.ccw(a[0], a[k1], a[k2]) != 0) break;
hull.push(a[k2 - 1]);
for (int i = k2; i < n; i++) {
Point2D top = hull.pop();
while (Point2D.ccw(hull.peek(), top, a[i]) <= 0) {
top = hull.pop();
}
hull.push(top);
hull.push(a[i]);
}
assert isConvex();
}
public Iterable<Point2D> hull() {
Stack<Point2D> s = new Stack<Point2D>();
for (Point2D p : hull) s.push(p);
return s;
}
private boolean isConvex() {
int n = hull.size();
if (n <= 2) return true;
Point2D[] points = new Point2D[n];
int k = 0;
for (Point2D p : hull()) {
points[k++] = p;
}
for (int i = 0; i < n; i++) {
if (Point2D.ccw(points[i], points[(i + 1) % n], points[(i + 2) % n]) <= 0) {
return false;
}
}
return true;
}
}
#ifndef GRAHAMSCAN_H
#define GRAHAMSCAN_H
#include "Point2D.h"
#include <vector>
#include <stack>
class GrahamScan {
private:
std::stack<Point2D> hull;
[[nodiscard]] bool isConvex() const;
public:
explicit GrahamScan(std::vector<Point2D>& points);
[[nodiscard]] std::vector<Point2D> hullPoints() const;
};
#endif // GRAHAMSCAN_H
#include <algorithm>
#include "GrahamScan.h"
GrahamScan::GrahamScan(std::vector<Point2D>& points) {
if (points.empty()) throw std::invalid_argument("array is of length 0");
const int n = static_cast<int>(points.size());
std::ranges::sort(points, [](const Point2D& a, const Point2D& b) {
return a.compareTo(b) < 0;
});
std::sort(points.begin() + 1, points.end(), Point2D::PolarOrder(points[0]));
hull.push(points[0]);
int k1;
for (k1 = 1; k1 < n; k1++)
if (points[0] != points[k1]) break;
if (k1 == n) return;
int k2;
for (k2 = k1 + 1; k2 < n; k2++)
if (Point2D::ccw(points[0], points[k1], points[k2]) != 0) break;
hull.push(points[k2 - 1]);
for (int i = k2; i < n; i++) {
Point2D top = hull.top();
hull.pop();
while (Point2D::ccw(hull.top(), top, points[i]) <= 0) {
top = hull.top();
hull.pop();
}
hull.push(top);
hull.push(points[i]);
}
}
std::vector<Point2D> GrahamScan::hullPoints() const {
std::vector<Point2D> s;
std::stack<Point2D> tempHull = hull;
while (!tempHull.empty()) {
s.push_back(tempHull.top());
tempHull.pop();
}
std::ranges::reverse(s);
return s;
}
bool GrahamScan::isConvex() const {
const int n = static_cast<int>(hull.size());
if (n <= 2) return true;
const std::vector<Point2D> points = hullPoints();
for (int i = 0; i < n; i++) {
if (Point2D::ccw(points[i], points[(i + 1) % n], points[(i + 2) % n]) <= 0) {
return false;
}
}
return true;
}
from Point2D import Point2D
class GrahamScan:
def __init__(self, points):
if points is None:
raise ValueError("argument is null")
if not points:
raise ValueError("array is of length 0")
n = len(points)
a = sorted(points)
def polar_order(p1, p2):
dx1 = p1.x - a[0].x
dy1 = p1.y - a[0].y
dx2 = p2.x - a[0].x
dy2 = p2.y - a[0].y
if dy1 >= 0 > dy2:
return -1
elif dy2 >= 0 > dy1:
return +1
elif dy1 == 0 and dy2 == 0:
if dx1 >= 0 > dx2:
return -1
elif dx2 >= 0 > dx1:
return +1
else:
return 0
else:
return -Point2D.ccw(a[0], p1, p2)
a[1:] = sorted(a[1:], key=lambda p: (p.y - a[0].y, p.x - a[0].x))
self.hull = [a[0], a[1]]
for i in range(2, n):
top = self.hull.pop()
while Point2D.ccw(self.hull[-1], top, a[i]) <= 0:
top = self.hull.pop()
self.hull.append(top)
self.hull.append(a[i])
def hull_points(self):
return self.hull
def _is_convex(self):
n = len(self.hull)
if n <= 2:
return True
for i in range(n):
if Point2D.ccw(self.hull[i], self.hull[(i + 1) % n], self.hull[(i + 2) % n]) <= 0:
return False
return True
6. Mergesort
6.1 Mergesort
Time complexity:
. Space complexity:
.
Merge Sort
Divide the array into two halves.
Recursively sort each half.
Merge two halves.
In-place: A sorting algorithm is in-place if it uses
Example: Insertion sort, selection sort, shellsort.
Property: Mergesort uses at most
Proof
The number of compares
->
Prove
And we have:
import java.util.Comparator;
public class Merge {
private static <T> void merge(T[] a, T[] aux, int lo, int mid, int hi, Comparator<T>
comparator) {
System.arraycopy(a, lo, aux, lo, hi - lo + 1);
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (comparator.compare(aux[j], aux[i]) < 0) a[k] = aux[j++]; // Correct comparison
else a[k] = aux[i++];
}
}
private static <T> void sort(T[] a, T[] aux, int lo, int hi, Comparator<T>
comparator) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid, comparator);
sort(a, aux, mid + 1, hi, comparator);
merge(a, aux, lo, mid, hi, comparator);
}
public static <T> void sort(T[] a, Comparator<T> comparator) {
T[] aux = (T[]) new Object[a.length];
sort(a, aux, 0, a.length - 1, comparator);
}
}
#include <iostream>
#include <functional> // For std::less (optional)
template <typename T, typename Comparator = std::less<>>
void merge(T arr[], T aux[], const int lo, const int mid, const int hi, Comparator comparator =
{}) {
for (int k = lo; k <= hi; k++) {
aux[k] = arr[k];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) arr[k] = aux[j++];
else if (j > hi) arr[k] = aux[i++];
else if (comparator(aux[j], aux[i])) arr[k] = aux[j++];
else arr[k] = aux[i++];
}
}
template <typename T, typename Comparator>
void mergeSort(T arr[], T aux[], int lo, int hi, Comparator comparator) {
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
mergeSort(arr, aux, lo, mid, comparator);
mergeSort(arr, aux, mid + 1, hi, comparator);
merge(arr, aux, lo, mid, hi, comparator);
}
template <typename T, typename Comparator = std::less<>>
void mergeSort(T arr[], const int size, Comparator comparator = {}) {
T* aux = new T[size];
mergeSort(arr, aux, 0, size - 1, comparator); // Call the correct overload
delete[] aux;
}
def merge_sort(arr, comparator=lambda x, y: x < y):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half, comparator)
merge_sort(right_half, comparator)
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if comparator(left_half[i], right_half[j]):
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
6.2 Bottom-Up Mergesort
Bottom-Up Mergesort
Pass through array, merging subarrays of size 1.
Repeat for subarrays of size 2, 4, 8, 16, ...
public class MergeBU {
private static Comparable[] aux;
private static void merge(Comparable[]a, int lo, int mid, int hi) {
assert isSorted(a, lo, mid); // precondition: a[lo...mid] is sorted
assert isSorted(a, mid+1, hi); // precondition: a[mid+1...hi] is sorted
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (less(aux[j], aux[i])) a[k] = aux[j++];
else a[k] = aux[i++];
}
assert isSorted(a, lo, hi); // postcondition: a[lo...hi] is sorted
}
private static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
public static void sort(Comparable[]a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz++)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));
}
private static boolean isSorted(Comparable[] a, int lo, int hi) {
for (int i = lo + 1; i <= hi; i++)
if (less(a[i], a[i-1])) return false;
return true;
}
}
#include <vector>
#include <algorithm>
class MergeBU {
public:
static void merge(std::vector<int>& a, int lo, int mid, int hi) {
std::vector<int> aux(a);
int i = lo, j = mid+1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
else if (aux[j] < aux[i]) a[k] = aux[j++];
else a[k] = aux[i++];
}
}
static void sort(std::vector<int>& a) {
int N = a.size();
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, std::min(lo+sz+sz-1, N-1));
}
};
def merge(a, lo, mid, hi):
aux = a.copy()
i = lo
j = mid + 1
for k in range(lo, hi + 1):
if i > mid:
a[k] = aux[j]
j += 1
elif j > hi:
a[k] = aux[i]
i += 1
elif aux[j] < aux[i]:
a[k] = aux[j]
j += 1
else:
a[k] = aux[i]
i += 1
assert a[lo:hi + 1] == sorted(a[lo:hi + 1]), "Array is not sorted"
def sort(a):
N = len(a)
sz = 1
while sz < N:
lo = 0
while lo < N - sz:
merge(a, lo, lo + sz - 1, min(lo + sz + sz - 1, N - 1))
lo += sz + sz
sz += 1
6.3 Computational Complexity
Definitions
Computational complexity: Framework to study efficiency of algorithms for solving a particular problem
. Model of computation: Allowable operations.
Cost model: Operation count(s).
Upper bound: Cost guarantee provided by some algorithm for
. Lower bound: Proven limit on cost guarantee of all algorithms for
. Optimal algorithm: Algorithm with best possible cost guarantee for
.
Example: sorting
Model of computation: decision tree (can access information only through compares).
Cost model: Number of compares .
Upper bound:
from mergesort. Lower bound:
. Optimal algorithm = mergesort.
Property: Any compare-based sorting algorithm must use at least
Proof
Assume array consists of
distinct values through . Worst case dictated by height
of decision tree. Binary tree of height
has at most leaves. different orderings => at least leaves.
6.4 Stability
Stability: A stable sort preserves the relative order of items with equal keys.
Methods
Need to carefully check the code ("less than" vs " less than or equal to"). Equal items never move past each other -> stable sort.
Counterexample: Long-distance exchange might move an item past some equal item.
Conclusion
Stable sort: Insertion sort, mergesort, bubble sort, radix sort, etc.
Unstable sort: Selection sort, shellsort, quicksort, heapsort, etc.
7 Quicksort
7.1 Quicksort
Quicksort
Shuffle the array.
Partition so that, for some
: Entry
a[j]is in place;No larger entry to the left of
; No smaller entry to the right of
.
Sort each piece recursively .
Quicksort Partitioning
Scan
from left to right so long as (a[i] < a[lo]). Scan
from right to left so long as (a[j] > a[lo]). Exchange a[i] with a[j], repeat until
and pointers cross. When pointers cross, Exchange a[lo] with a[j].
Runtime Analysis
Time complexity:
. Best case: Number of compares is
. Worst case: Number of compares is
.
Property: The average number of compares
Proof
Multiply both sides by
and collect terms: Subtract this from the same equation for
: Repeatedly apply above equation:
Approximate sum by integral:
Finally, desired result:
Quicksort is an in-place, non-stable sorting algorithm.
Summary of performance characteristics:
Worst case: Number of compares are quadratic.
More likely that your computer is struck by lightning bolt.
Average case: Number of compares is
. 39% more compares than mergesort.
But faster than mergesort in practice because of less data movement.
Random shuffle
Probabilistic guarantee against worst case.
Basis for math model that can be validated with experiments .
Caveat emptor
Many textbook implementations go quadratic if array:
Is sorted or reverse sorted.
Has many duplicates (even if randomized!)
import java.util.Comparator;
public class Quick {
private static final int CUTOFF = 10;
private static <T> int partition(T[] a, int lo, int hi, Comparator<? super T>
comparator) {
int i = lo, j = hi + 1;
while (true) {
while (comparator.compare(a[++i], a[lo]) < 0) {
if (i == hi) break;
}
while (j > lo && comparator.compare(a[lo], a[--j]) < 0) {
if (j == lo) break;
}
if (i >= j) break;
exch(a, i, j);
}
exch(a, lo, j);
return j;
}
public static <T> void sort(T[] a, Comparator<? super T> comparator) {
sort(a, 0, a.length - 1, comparator);
}
private static <T> void sort(T[] a, int lo, int hi, Comparator<? super T>
comparator) {
if (hi <= lo + CUTOFF - 1) {
insertionSort(a, lo, hi, comparator);
return;
}
int j = partition(a, lo, hi, comparator);
sort(a, lo, j - 1, comparator);
sort(a, j + 1, hi, comparator);
}
private static <T> void insertionSort(T[] a, int lo, int hi, Comparator<? super T>
comparator) {
for (int i = lo + 1; i <= hi; i++) {
for (int j = i; j > lo && comparator.compare(a[j], a[j - 1]) < 0; j--) {
exch(a, j, j - 1);
}
}
}
private static <T> void exch(T[] a, int i, int j) {
T swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
#include <iostream>
#include <functional>
#include <algorithm>
template <typename T, typename Comparator = std::less<>>
int partition(T arr[], int lo, const int hi, Comparator comparator = {}) {
int i = lo, j = hi + 1;
while (true) {
while (comparator(arr[++i], arr[lo])) {
if (i == hi) break;
}
while (j > lo && comparator(arr[lo], arr[--j])) {
if (j == lo) break;
}
if (i >= j) break;
std::swap(arr[i], arr[j]);
}
std::swap(arr[lo], arr[j]);
return j;
}
template <typename T, typename Comparator = std::less<>>
void sort(T arr[], int lo, int hi, Comparator comparator = {}) {
constexpr int CUTOFF = 10;
if (hi <= lo + CUTOFF - 1) {
std::sort(arr + lo, arr + hi + 1, comparator);
return;
}
const int j = partition(arr, lo, hi, comparator);
sort(arr, lo, j - 1, comparator);
sort(arr, j + 1, hi, comparator);
}
template <typename T, typename Comparator = std::less<>>
void sort(T arr[], const int n, Comparator comparator = {}) {
sort(arr, 0, n - 1, comparator);
}
def partition(arr, lo, hi, comparator):
i, j = lo, hi + 1
while True:
while comparator(arr[i + 1], arr[lo]) < 0:
i += 1
if i == hi:
break
while comparator(arr[lo], arr[j - 1]) < 0 and j > lo:
j -= 1
if j == lo:
break
if i >= j:
break
arr[i], arr[j] = arr[j], arr[i]
arr[lo], arr[j] = arr[j], arr[lo]
return j
def insertion_sort(arr, lo, hi, comparator):
for i in range(lo + 1, hi + 1):
j = i
while j > lo and comparator(arr[j], arr[j - 1]) < 0:
arr[j], arr[j - 1] = arr[j - 1], arr[j]
j -= 1
def sort(arr, lo, hi, comparator):
CUTOFF = 10
if hi <= lo + CUTOFF - 1:
insertion_sort(arr, lo, hi, comparator)
return
j = partition(arr, lo, hi, comparator)
sort(arr, lo, j - 1, comparator)
sort(arr, j + 1, hi, comparator)
def quicksort(arr, comparator=lambda x, y: x < y):
sort(arr, 0, len(arr) - 1, comparator)
7.2 Selection
Goal: Given an array of
Quick Selection
Partition array so that entry
a[j]is in place.Repeat in one subarray, depending on
; finished when equals .
Property: Quick-select takes linear time on average.
Proof
Intuitively, each partitioning step splits array approximately in half:
compares. Formal analysis similar to quicksort analysis yields:
to find the median
public static <T> T select(T[] a, int k, Comparator<? super T> comparator) {
int lo = 0, hi = a.length - 1;
while (hi > lo) {
int j = partition(a, lo, hi, comparator);
if (j < k) lo = j + 1;
else if (j > k) hi = j - 1;
else return a[k];
}
return a[k];
}
template <typename T, typename Comparator = std::less<>>
T select(T arr[], int k, int lo, int hi, Comparator comparator = {}) {
while (hi > lo) {
int j = partition(arr, lo, hi, comparator);
if (j < k) lo = j + 1;
else if (j > k) hi = j - 1;
else return arr[k];
}
return arr[k];
}
template <typename T, typename Comparator = std::less<>>
T select(T arr[], const int n, int k, Comparator comparator = {}) {
return select(arr, k, 0, n - 1, comparator);
}
def select(arr, k, lo, hi, comparator):
while hi > lo:
j = partition(arr, lo, hi, comparator)
if j < k:
lo = j + 1
elif j > k:
hi = j - 1
else:
return arr[k]
return arr[k]
def quickselect(arr, k, comparator=lambda x, y: x < y):
return select(arr, k, 0, len(arr) - 1, comparator)
7.3 Duplicate Keys
Problem of quicksort with duplicate keys
Mergesort with duplicate keys: Always between
and compares. Quicksort with duplicate keys: Algorithm goes quadratic unless partitioning stops on equal keys.
Goal: Partitioning array into 3 parts so that:
Entries between lt and gt equal to partitioning item v.
No larger entries to left of lt.
No smaller entries to right of gt.
Dijkstra 3-way Partitioning
Let v be partitioning item a[lo].
Scan i from left to right.
a[i] < v: exchange a[lt] with a[i]; increment both
and . a[i] > v: exchange a[gt] with a[i]; decrement
. a[i] == v: increment
.
Sorting lower bound: If there are
compares in the worst case (
Property: Quicksort with 3-way partitioning is entropy-optimal.
import java.util.Comparator;
public class Dijkstra3WayPartition {
private static final int CUTOFF = 10;
private static <T> void sort(T[] a, Comparator<? super T> comparator) {
sort(a, 0, a.length - 1, comparator);
}
private static <T> void sort(T[] a, int lo, int hi, Comparator<? super T>
comparator) {
if (hi <= lo + CUTOFF - 1) {
insertionSort(a, lo, hi, comparator);
return;
}
int lt = lo, gt = hi;
T v = a[lo];
int i = lo + 1;
while (i <= gt) {
int cmp = comparator.compare(a[i], v);
if (cmp < 0) exch(a, lt++, i++);
else if (cmp > 0) exch(a, i, gt--);
else i++;
}
sort(a, lo, lt - 1, comparator);
sort(a, gt + 1, hi, comparator);
}
private static <T> void insertionSort(T[] a, int lo, int hi, Comparator<? super T>
comparator) {
for (int i = lo + 1; i <= hi; i++) {
for (int j = i; j > lo && comparator.compare(a[j], a[j - 1]) < 0; j--) {
exch(a, j, j - 1);
}
}
}
private static <T> void exch(T[] a, int i, int j) {
T swap = a[i];
a[i] = a[j];
a[j] = swap;
}
}
#include <functional>
#include <algorithm>
template <typename T, typename Comparator = std::less<>>
void sort(T arr[], int lo, int hi, Comparator comparator = {}) {
constexpr int CUTOFF = 10;
if (hi <= lo + CUTOFF - 1) {
std::sort(arr + lo, arr + hi + 1, comparator);
return;
}
int lt = lo, gt = hi;
T v = arr[lo];
int i = lo + 1;
while (i <= gt) {
if (comparator(arr[i], v)) std::swap(arr[lt++], arr[i++]);
else if (comparator(v, arr[i])) std::swap(arr[i], arr[gt--]);
else i++;
}
sort(arr, lo, lt - 1, comparator);
sort(arr, gt + 1, hi, comparator);
}
template <typename T, typename Comparator = std::less<>>
void sort(T arr[], const int n, Comparator comparator = {}) {
sort(arr, 0, n - 1, comparator);
}
def sort(arr: list, lo: int, hi: int):
CUTOFF = 10
if hi <= lo + CUTOFF - 1:
arr[lo:hi+1] = sorted(arr[lo:hi+1])
return
lt = lo
gt = hi
v = arr[lo]
i = lo + 1
while i <= gt:
if arr[i] < v:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1
i += 1
elif arr[i] > v:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1
else:
i += 1
sort(arr, lo, lt - 1)
sort(arr, gt + 1, hi)
def sort_all(arr: list):
sort(arr, 0, len(arr) - 1)
Conclusion
8 Priority Queues
8.1 API and Elementary Implementations
Applications
Event-driven simulation [customers in a line, colliding particles]
Numerical computation [reducing roundoff error]
Data compression [Huffman codes]
Graph searching [Dijkstra's algorithm, Prim's algorithm]
Number theory [sum of powers]
Artificial intelligence [A* search]
Statistics [maintain largest M values in a sequence]
Operating systems [load balancing, interrupt handling]
Discrete optimization [bin packing, scheduling]
Spam filtering [Bayesian spam filter]
Built-in Implementation
import java.util.PriorityQueue;
public class PQ {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
pq.add(10);
pq.add(20);
pq.add(15);
System.out.println(pq.peek()); // Outputs 10
System.out.println(pq.poll()); // Outputs 10 (Contains Removal)
System.out.println(pq.peek()); // Outputs 15
}
}
#include <iostream>
#include <queue>
#include <vector>
int main() {
std::priority_queue<std::pair<int, int>> pq;
pq.emplace(3, 100); // 100 has priority 3
pq.emplace(1, 40); // 40 has priority 1
pq.emplace(2, 60); // 60 has priority 2
while (!pq.empty()) {
std::cout << "Value: " << pq.top().second << ", Priority: " <<
pq.top().first << std::endl;
pq.pop();
}
return 0;
}
import heapq
# Create a priority queue
priority_queue = []
# Add elements with priorities
heapq.heappush(priority_queue, (2, 'code'))
heapq.heappush(priority_queue, (1, 'eat'))
heapq.heappush(priority_queue, (3, 'sleep'))
# Remove and return the highest priority task
task = heapq.heappop(priority_queue)[1]
print(task) # Outputs: 'eat'
Unordered Array Implementation
import java.util.Comparator;
public class UnorderedArrayMaxPQ<Key> {
private final Key[] pq;
private int n;
private final Comparator<Key> comparator;
public UnorderedArrayMaxPQ(int capacity, Comparator<Key> comparator) {
pq = (Key[]) new Object[capacity];
n = 0;
this.comparator = comparator;
}
public boolean isEmpty() {
return n == 0;
}
public int size() {
return n;
}
public void insert(Key x) {
pq[n++] = x;
}
public Key delMax() {
int max = 0;
for (int i = 1; i < n; i++)
if (comparator.compare(pq[max], pq[i]) < 0) max = i;
exch(max, n - 1);
return pq[--n];
}
private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}
}
#include <iostream>
#include <functional>
#include <algorithm>
template <typename Key, typename Comparator = std::less<Key>>
class UnorderedArrayMaxPQ {
private:
Key* pq;
int n;
Comparator comparator;
public:
explicit UnorderedArrayMaxPQ(const int capacity, Comparator comparator = {}) :
pq(new Key[capacity]), n(0), comparator(comparator) {}
~UnorderedArrayMaxPQ() { delete[] pq; }
[[nodiscard]] bool isEmpty() const { return n == 0; }
[[nodiscard]] int size() const { return n; }
void insert(const Key& x) { pq[n++] = x; }
Key delMax() {
int max = 0;
for (int i = 1; i < n; i++) {
if (comparator(pq[max], pq[i])) {
max = i;
}
}
std::swap(pq[max], pq[n - 1]);
return pq[--n];
}
};
from typing import Generic, TypeVar, Callable, Optional
Key = TypeVar("Key")
class UnorderedArrayMaxPQ(Generic[Key]):
def __init__(self, capacity: int, comparator: Optional[Callable[[Key, Key], bool]] = None) ->
None:
self.pq: list[Key] = [None] * capacity
self.n: int = 0
if comparator is None:
self.comparator = lambda a, b: a < b # Default to less-than comparison
else:
self.comparator = comparator
def isEmpty(self) -> bool:
return self.n == 0
def size(self) -> int:
return self.n
def insert(self, x: Key) -> None:
self.pq[self.n] = x
self.n += 1
def delMax(self) -> Key:
max_index: int = 0
for i in range(1, self.n):
if self.comparator(self.pq[max_index], self.pq[i]):
max_index = i
self.pq[max_index], self.pq[self.n - 1] = self.pq[self.n - 1], self.pq[max_index]
self.n -= 1
return self.pq[self.n]
Ordered Array Implementation
import java.util.Comparator;
public class OrderedArrayMaxPQ<Key> {
private final Key[] pq;
private int n;
private final Comparator<Key> comparator;
public OrderedArrayMaxPQ(int capacity, Comparator<Key> comparator) {
pq = (Key[]) new Object[capacity];
n = 0;
this.comparator = comparator;
}
public boolean isEmpty() {
return n == 0;
}
public int size() {
return n;
}
public Key delMax() {
return pq[--n];
}
public void insert(Key key) {
int i = n - 1;
while (i >= 0 && comparator.compare(key, pq[i]) < 0) { // Use comparator
pq[i + 1] = pq[i];
i--;
}
pq[i + 1] = key;
n++;
}
}
#include <iostream>
#include <functional>
template <typename Key, typename Comparator = std::less<Key>>
class OrderedArrayMaxPQ {
private:
Key* pq;
int n;
Comparator comparator;
public:
explicit OrderedArrayMaxPQ(const int capacity, Comparator comparator = {}) :
pq(new Key[capacity]), n(0), comparator(comparator) {}
~OrderedArrayMaxPQ() { delete[] pq; }
[[nodiscard]] bool isEmpty() const { return n == 0; }
[[nodiscard]] int size() const { return n; }
Key delMax() { return pq[--n]; }
void insert(const Key& key) {
int i = n - 1;
while (i >= 0 && comparator(key, pq[i])) { // Use comparator
pq[i + 1] = pq[i];
i--;
}
pq[i + 1] = key;
n++;
}
};
from typing import Generic, TypeVar, Callable, Optional
Key = TypeVar("Key")
class OrderedArrayMaxPQ(Generic[Key]):
def __init__(self, capacity: int, comparator: Optional[Callable[[Key, Key], bool]] = None) ->
None:
self.pq: list[Key] = [None] * capacity
self.n: int = 0
if comparator is None:
self.comparator = lambda a, b: a < b
else:
self.comparator = comparator
def isEmpty(self) -> bool:
return self.n == 0
def size(self) -> int:
return self.n
def delMax(self) -> Key:
self.n -= 1
return self.pq[self.n]
def insert(self, key: Key) -> None:
i: int = self.n - 1
while i >= 0 and self.comparator(key, self.pq[i]):
self.pq[i + 1] = self.pq[i]
i -= 1
self.pq[i + 1] = key
self.n += 1
8.2 Binary Heap
8.1.1 Concepts & Properties
Definitions:
Binary tree: Empty or node with links to left and right binary trees.
Complete binary tree: Perfectly balanced, except for bottom level.
Binary heap: Array representation of a heap-ordered complete binary tree.
Property of complete binary tree: Height of complete binary tree with
Proof: Height only increases when
Properties of Binary Heap:
Key in nodes.
Parent's key no smaller than children's keys.
Largest key is
a[1], which is root of binary tree.Can use array indices to move through tree.
Parent of node at
is at . Children of node at
are at and .
8.1.2 Binary-Heap Implementation of Priority Queues
Violation in Binary Heap (Child's key becomes larger key than its parent's key
Exchange key in child with key in parent.
Repeat until heap order restored.
Insertion in Binary Heap
Add node at end, then swim it up.
At most
compares.
Demotion in Binary Heap (Parent's key becomes smaller than one (or both) of its children's
Exchange key in parent with key in larger child.
Repeat until heap order restored.
Deletion in Binary Heap
Exchange root with node at end, then sink it down.
At most
compares.
import java.util.Comparator;
import java.util.NoSuchElementException;
public class MaxPQ<Key> {
private Key[] pq;
private int n;
private Comparator<Key> comparator;
public MaxPQ(int initCapacity) {
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}
public MaxPQ() {
this(1);
}
public MaxPQ(int initCapacity, Comparator<Key> comparator) {
this.comparator = comparator;
pq = (Key[]) new Object[initCapacity + 1];
n = 0;
}
public MaxPQ(Comparator<Key> comparator) {
this(1, comparator);
}
public MaxPQ(Key[] keys) {
n = keys.length;
pq = (Key[]) new Object[keys.length + 1];
for (int i = 0; i < n; i++)
pq[i+1] = keys[i];
for (int k = n/2; k >= 1; k--)
sink(k);
assert isMaxHeap();
}
public boolean isEmpty() {
return n == 0;
}
public int size() {
return n;
}
public Key max() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
return pq[1];
}
private void resize(int capacity) {
assert capacity > n;
Key[] temp = (Key[]) new Object[capacity];
if (n >= 0) System.arraycopy(pq, 1, temp, 1, n);
pq = temp;
}
public void insert(Key x) {
if (n == pq.length - 1) resize(2 * pq.length);
pq[++n] = x;
swim(n);
assert isMaxHeap();
}
public Key delMax() {
if (isEmpty()) throw new NoSuchElementException("Priority queue underflow");
Key max = pq[1];
exch(1, n--);
sink(1);
pq[n+1] = null;
if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
assert isMaxHeap();
return max;
}
private void swim(int k) {
while (k > 1 && less(k/2, k)) {
exch(k/2, k);
k = k/2;
}
}
private void sink(int k) {
while (2*k <= n) {
int j = 2*k;
if (j < n && less(j, j+1)) j++;
if (!less(k, j)) break;
exch(k, j);
k = j;
}
}
private boolean less(int i, int j) {
if (comparator == null) {
return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
}
else {
return comparator.compare(pq[i], pq[j]) < 0;
}
}
private void exch(int i, int j) {
Key swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
}
private boolean isMaxHeap() {
for (int i = 1; i <= n; i++) {
if (pq[i] == null) return false;
}
for (int i = n+1; i < pq.length; i++) {
if (pq[i] != null) return false;
}
if (pq[0] != null) return false;
return isMaxHeapOrdered(1);
}
private boolean isMaxHeapOrdered(int k) {
if (k > n) return true;
int left = 2*k;
int right = 2*k + 1;
if (left <= n && less(k, left)) return false;
if (right <= n && less(k, right)) return false;
return isMaxHeapOrdered(left) && isMaxHeapOrdered(right);
}
}
#include <iostream>
#include <functional>
#include <algorithm>
#include <cassert>
#include <stdexcept>
template <typename Key, typename Comparator = std::less<Key>>
class MaxPQ {
private:
Key* pq;
int n;
Comparator comparator;
void resize(const int capacity) {
assert(capacity > n);
Key* temp = new Key[capacity];
std::copy(pq + 1, pq + n + 1, temp + 1);
delete[] pq;
pq = temp;
}
void swim(int k) {
while (k > 1 && comparator(pq[k / 2], pq[k])) {
std::swap(pq[k / 2], pq[k]);
k = k / 2;
}
}
void sink(int k) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && comparator(pq[j], pq[j + 1])) j++;
if (!comparator(pq[k], pq[j])) break;
std::swap(pq[k], pq[j]);
k = j;
}
}
bool isMaxHeap() {
for (int i = 1; i <= n; i++) {
if (pq[i] == nullptr) return false;
}
for (int i = n+1; i < pq.length; i++) {
if (pq[i] != nullptr) return false;
}
if (pq[0] != nullptr) return false;
return isMaxHeapOrdered(1);
}
bool isMaxHeapOrdered(int k) {
if (k > n) return true;
int left = 2 * k;
int right = 2 * k + 1;
if (left <= n && comparator(pq[k], pq[left])) return false;
if (right <= n && comparator(pq[k], pq[right])) return false;
return isMaxHeapOrdered(left) && isMaxHeapOrdered(right);
}
public:
explicit MaxPQ(const int initCapacity, Comparator comparator = {}) :
pq(new Key[initCapacity + 1]), n(0), comparator(comparator) {}
explicit MaxPQ(int initCapacity) : MaxPQ(initCapacity, Comparator{}) {}
explicit MaxPQ(Comparator comparator) : MaxPQ(1, comparator) {}
MaxPQ() : MaxPQ(1, Comparator{}) {}
MaxPQ(const Key* keys, int size) : MaxPQ(size) {
n = size;
std::copy(keys, keys + size, pq + 1);
for (int k = n / 2; k >= 1; k--)
sink(k);
assert(isMaxHeap());
}
~MaxPQ() { delete[] pq; }
[[nodiscard]] bool isEmpty() const { return n == 0; }
[[nodiscard]] int size() const { return n; }
Key max() {
if (isEmpty()) throw std::runtime_error("Priority queue underflow");
return pq[1];
}
void insert(const Key& x) {
if (n == pq.length - 1) resize(2 * pq.length);
pq[++n] = x;
swim(n);
assert(isMaxHeap());
}
Key delMax() {
if (isEmpty()) throw std::runtime_error("Priority queue underflow");
Key max = pq[1];
std::swap(pq[1], pq[n--]);
sink(1);
if ((n > 0) && (n == (pq.length - 1) / 4)) resize(pq.length / 2);
assert(isMaxHeap());
return max;
}
};
class MaxPQ:
def __init__(self, capacity, key=lambda x: x):
self.pq = [None] * (capacity + 1)
self.n = 0
self.key = key
def is_empty(self):
return self.n == 0
def size(self):
return self.n
def insert(self, item):
if self.n == len(self.pq) - 1:
self._resize(2 * len(self.pq))
self.n += 1
self.pq[self.n] = item
self._swim(self.n)
def max(self):
if self.is_empty():
raise IndexError("Priority queue is empty")
return self.pq[1]
def del_max(self):
if self.is_empty():
raise IndexError("Priority queue is empty")
max_item = self.pq[1]
self._exch(1, self.n)
self.n -= 1
self.pq[self.n + 1] = None
self._sink(1)
if self.n > 0 and self.n == (len(self.pq) - 1) // 4:
self._resize(len(self.pq) // 2)
return max_item
def _swim(self, k):
while k > 1 and self._less(k // 2, k):
self._exch(k // 2, k)
k //= 2
def _sink(self, k):
while 2 * k <= self.n:
j = 2 * k
if j < self.n and self._less(j, j + 1):
j += 1
if not self._less(k, j):
break
self._exch(k, j)
k = j
def _less(self, i, j):
return self.key(self.pq[i]) < self.key(self.pq[j])
def _exch(self, i, j):
self.pq[i], self.pq[j] = self.pq[j], self.pq[i]
def _resize(self, capacity):
temp = [None] * capacity
for i in range(1, self.n + 1):
temp[i] = self.pq[i]
self.pq = temp
8.3 Indexed Priority Queue
Indexed Priority Queue: Associate an index between
Client can insert and delete-the-minimum.
Client can change the key by specifying the index.
Indexed Priority Queue
Start with same code as MinPQ.
Maintain parallel arrays keys[], pq[] and qp[] so that:
keys[i] is the priority of i.
pq[i] is the index of the key in heap position i.
qp[i] is the heap position of the key with index i .
Use swim(qp[i]) implement decreaseKey(i, key).
import java.util.NoSuchElementException;
public class IndexedPriorityQueue {
private final int maxN;
private int n;
private final int[] pq;
private final int[] qp;
private final double[] keys;
public IndexedPriorityQueue(int maxN) {
if (maxN < 0) throw new IllegalArgumentException();
this.maxN = maxN;
n = 0;
keys = new double[maxN + 1];
pq = new int[maxN + 1];
qp = new int[maxN + 1];
for (int i = 0; i <= maxN; i++) qp[i] = -1;
}
public boolean isEmpty() {
return n == 0;
}
public boolean contains(int i) {
return qp[i] != -1;
}
public int size() {
return n;
}
public void insert(int i, double key) {
if (contains(i)) throw new IllegalArgumentException("Index is already in the priority queue");
n++;
qp[i] = n;
pq[n] = i;
keys[i] = key;
swim(n);
}
public int delMin() {
if (n == 0) throw new NoSuchElementException("Priority queue underflow");
int min = pq[1];
exch(1, n--);
sink(1);
qp[min] = -1;
pq[n + 1] = -1;
return min;
}
public void decreaseKey(int i, double key) {
if (!contains(i)) throw new NoSuchElementException("Index is not in the priority queue");
if (keys[i] <= key) throw new IllegalArgumentException("Calling decreaseKey() with a key
greater than or equal to the key in the priority queue");
keys[i] = key;
swim(qp[i]);
}
private boolean greater(int i, int j) {
return keys[pq[i]] > keys[pq[j]];
}
private void exch(int i, int j) {
int swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
private void swim(int k) {
while (k > 1 && greater(k / 2, k)) {
exch(k, k / 2);
k = k / 2;
}
}
private void sink(int k) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && greater(j, j + 1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}
}
#ifndef INDEXED_PRIORITY_QUEUE_H
#define INDEXED_PRIORITY_QUEUE_H
#include <vector>
class IndexedPriorityQueue {
public:
explicit IndexedPriorityQueue(int maxN);
[[nodiscard]] bool isEmpty() const;
[[nodiscard]] bool contains(int i) const;
[[nodiscard]] int size() const;
void insert(int i, double key);
int delMin();
void decreaseKey(int i, double key);
private:
int maxN;
int n;
std::vector<int> pq;
std::vector<int> qp;
std::vector<double> keys;
[[nodiscard]] bool greater(int i, int j) const;
void exch(int i, int j);
void swim(int k);
void sink(int k);
};
#endif // INDEXED_PRIORITY_QUEUE_H
#include "IndexedPriorityQueue.h"
#include <stdexcept>
IndexedPriorityQueue::IndexedPriorityQueue(const int maxN) : maxN(maxN), n(0), pq(maxN + 1),
qp(maxN + 1, -1), keys(maxN + 1) {
if (maxN < 0) throw std::invalid_argument("maxN must be non-negative");
}
bool IndexedPriorityQueue::isEmpty() const {
return n == 0;
}
bool IndexedPriorityQueue::contains(int i) const {
return qp[i] != -1;
}
int IndexedPriorityQueue::size() const {
return n;
}
void IndexedPriorityQueue::insert(const int i, const double key) {
if (contains(i)) throw std::invalid_argument("Index is already in the priority queue");
n++;
qp[i] = n;
pq[n] = i;
keys[i] = key;
swim(n);
}
int IndexedPriorityQueue::delMin() {
if (n == 0) throw std::out_of_range("Priority queue underflow");
const int min = pq[1];
exch(1, n--);
sink(1);
qp[min] = -1;
pq[n + 1] = -1;
return min;
}
void IndexedPriorityQueue::decreaseKey(const int i, const double key) {
if (!contains(i)) throw std::out_of_range("Index is not in the priority queue");
if (keys[i] <= key) throw std::invalid_argument("Calling decreaseKey() with a key greater
than or equal to the key in the priority queue");
keys[i] = key;
swim(qp[i]);
}
bool IndexedPriorityQueue::greater(const int i, const int j) const {
return keys[pq[i]] > keys[pq[j]];
}
void IndexedPriorityQueue::exch(const int i, const int j) {
int swap = pq[i];
pq[i] = pq[j];
pq[j] = swap;
qp[pq[i]] = i;
qp[pq[j]] = j;
}
void IndexedPriorityQueue::swim(int k) {
while (k > 1 && greater(k / 2, k)) {
exch(k, k / 2);
k = k / 2;
}
}
void IndexedPriorityQueue::sink(int k) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && greater(j, j + 1)) j++;
if (!greater(k, j)) break;
exch(k, j);
k = j;
}
}
class IndexedPriorityQueue:
def __init__(self, maxN):
if maxN < 0:
raise ValueError("maxN must be non-negative")
self.maxN = maxN
self.n = 0
self.keys = [None] * (maxN + 1)
self.pq = [0] * (maxN + 1)
self.qp = [-1] * (maxN + 1)
def is_empty(self):
return self.n == 0
def contains(self, i):
return self.qp[i] != -1
def size(self):
return self.n
def insert(self, i, key):
if self.contains(i):
raise ValueError("Index is already in the priority queue")
self.n += 1
self.qp[i] = self.n
self.pq[self.n] = i
self.keys[i] = key
self.swim(self.n)
def del_min(self):
if self.n == 0:
raise IndexError("Priority queue underflow")
min_index = self.pq[1]
self.exch(1, self.n)
self.n -= 1
self.sink(1)
self.qp[min_index] = -1
self.pq[self.n + 1] = -1
return min_index
def decrease_key(self, i, key):
if not self.contains(i):
raise IndexError("Index is not in the priority queue")
if self.keys[i] <= key:
raise ValueError("Calling decrease_key() with a key greater than or equal to the key in the
priority queue")
self.keys[i] = key
self.swim(self.qp[i])
def greater(self, i, j):
return self.keys[self.pq[i]] > self.keys[self.pq[j]]
def exch(self, i, j):
self.pq[i], self.pq[j] = self.pq[j], self.pq[i]
self.qp[self.pq[i]] = i
self.qp[self.pq[j]] = j
def swim(self, k):
while k > 1 and self.greater(k // 2, k):
self.exch(k, k // 2)
k //= 2
def sink(self, k):
while 2 * k <= self.n:
j = 2 * k
if j < self.n and self.greater(j, j + 1):
j += 1
if not self.greater(k, j):
break
self.exch(k, j)
k = j
8.4 Heapsort
Heapsort
Heap construction: Build max heap using bottom-up method.
Sortdown: Repeatedly delete the largest remaining item.
Properties
Heap construction uses
compares and exchanges. Heapsort uses
compares and exchanges. Heapsort is an in-place algorithm with
worst-case.
import java.util.Comparator;
public class Heap {
private Heap() {
}
public static <T> void sort(T[] pq, Comparator<T> comparator) {
int n = pq.length;
for (int k = n / 2; k >= 1; k--)
sink(pq, k, n, comparator);
int k = n;
while (k > 1) {
exch(pq, 1, k--);
sink(pq, 1, k, comparator);
}
}
private static <T> void sink(T[] pq, int k, int n, Comparator<T> comparator) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && comparator.compare(pq[j - 1], pq[j]) < 0) j++;
if (comparator.compare(pq[k - 1], pq[j - 1]) >= 0) break; // Not less
exch(pq, k, j);
k = j;
}
}
private static void exch(Object[] pq, int i, int j) {
Object swap = pq[i - 1];
pq[i - 1] = pq[j - 1];
pq[j - 1] = swap;
}
private static <T> void show(T[] a) {
for (T t : a) {
System.out.println(t);
}
}
}
#include <iostream>
#include <functional>
#include <algorithm>
template <typename T, typename Comparator = std::less<T>>
class Heap {
private:
Heap() = default;
public:
static void sort(T* pq, const int n, Comparator comparator = {}) {
for (int k = n / 2; k >= 1; k--)
sink(pq, k, n, comparator);
int k = n;
while (k > 1) {
std::swap(pq[0], pq[k - 1]);
k--;
sink(pq, 1, k, comparator);
}
}
private:
static void sink(T* pq, int k, int n, Comparator comparator) {
while (2 * k <= n) {
int j = 2 * k;
if (j < n && comparator(pq[j - 1], pq[j])) j++;
if (!comparator(pq[k - 1], pq[j - 1])) break;
std::swap(pq[k - 1], pq[j - 1]);
k = j;
}
}
public:
static void show(T* a, const int n) {
for (int i = 0; i < n; i++) {
std::cout << a[i] << std::endl;
}
}
};
class Heap:
def __init__(self):
pass
@staticmethod
def sort(pq, comparator=lambda x, y: x < y):
n = len(pq)
for k in range(n // 2, 0, -1):
Heap._sink(pq, k, n, comparator)
k = n
while k > 1:
Heap._exch(pq, 1, k)
k -= 1
Heap._sink(pq, 1, k, comparator)
@staticmethod
def _sink(pq, k, n, comparator):
while 2 * k <= n:
j = 2 * k
if j < n and comparator(pq[j - 1], pq[j]):
j += 1
if not comparator(pq[k - 1], pq[j - 1]):
break
Heap._exch(pq, k, j)
k = j
@staticmethod
def _exch(pq, i, j):
pq[i - 1], pq[j - 1] = pq[j - 1], pq[i - 1]
@staticmethod
def show(a):
for item in a:
print(item)
Last modified: 25 November 2024