Pack for USPS priority mail
Tournament_tree.cpp TournamentTree.javaprivate static class TreeNode {
// Leaf: remaining capacity in the box.
// Non-leaf: max remaining capacity in the subtree.
public double cap;
// Stores the items in the leaf node.
public List<Integer> items = new ArrayList<>();
public TreeNode(double cap) {
this.cap = cap;
}
}
// Stores the complete binary tree. For tree_[i],
// left subtree is tree_[2i + 1], and right subtree is tree_[2i + 2].
private List<TreeNode> tree;
// Recursively inserts item in tournament tree.
private void insertHelper(int idx, int item, double cap) {
int left = (idx * 2) + 1, right = (idx * 2) + 2;
if (left < tree.size()) { // tree_[idx] is an internal node.
insertHelper(tree.get(left).cap >= cap ? left : right, item, cap);
tree.get(idx).cap = Math.max(tree.get(left).cap, tree.get(right).cap);
} else { // tree_[idx] is a leaf node.
tree.get(idx).cap -= cap;
tree.get(idx).items.add(item);
}
}
// n items, and each box has unit_cap.
public TournamentTree(int n, double unitCap) {
// Complete binary tree with n leafs has 2n - 1 nodes.
int count = (n * 2) - 1;
tree = new ArrayList<>(count);
for (int i = 0; i < count; i++) {
tree.add(new TreeNode(unitCap));
}
}
public void insert(int item, double itemCap) {
insertHelper(0, item, itemCap);
}
private void printLeaf() {
for (int i = 0; i < tree.size(); ++i) {
System.out.println("i = " + i + ", cap = " + tree.get(i).cap);
for (int item : tree.get(i).items) {
System.out.print(item + " ");
}
System.out.println();
}
}
