Data Structures in C++

Each program reads a plain-text command script from input.txt, executes the commands against the structure, prints query results to the console, and writes structure dumps to a named output file.

Dynamic array. Backed by a raw int*. Capacity starts at 10 and doubles on overflow: allocate a new buffer, copy elements across, delete[] the old one. findKth is O(1), find is a linear scan, insert and remove shift the tail so both are O(n). Destructor frees the backing array.

Linked stack. Singly linked list with a sentinel header node, so push and pop never special-case the empty list, they splice at head->next unconditionally. All three operations O(1). pop and top on empty print "Stack is empty" and return -1 rather than dereferencing null. Destructor walks the chain and frees every node.

Binary search tree. Unbalanced, recursive insert and delete. Deletion handles all three cases; the two-child case replaces the node's value with its in-order successor (minimum of the right subtree) and then deletes that successor from the right subtree. printTree is an in-order traversal, so the output file is sorted by construction. findMin walks the left spine, O(h).

Priority queue. Min-heap over a flat std::vector<HeapNode> using standard implicit-tree index arithmetic: parent = (i-1)/2, children at 2i+1 and 2i+2. Lower priority value means higher importance. insert percolates up, deleteMin moves the last element to the root and percolates down, both O(log n). increasePriorityValue(obj, dp) adds dp to the object's priority value and percolates down, demoting it; the name refers to the numeric value rising, not the item becoming more important. Object lookup is a linear scan of the heap array, O(n); a hash map from object to index would make it O(1) at the cost of maintaining that map through every swap.

Correction logged 2026-09-02: an earlier version of this note and of the repo README described increasePriorityValue as lowering a key and percolating up. That was wrong, and was caught by reading the source line by line. Do not restate the old version.

• No automated tests. Correctness was verified against the provided input scripts, not a test suite.
• No performance benchmarking. The complexity claims are from reading the code, not from measurement.
• The BST is unbalanced, so worst-case operations degrade to O(n) on sorted input. No AVL or red-black balancing was part of the assignment.
• Priority queue object lookup is O(n).