Chap 10 (HEAP/B-TREES)

What is a heap

A heap is a binary tree where elements follow total order semantics and satisfy two rules: each node is greater than or equal to its children, and the tree is a complete binary tree

What are the two heap storage rules

1) Each node's element is greater than or equal to its children

2) The tree must be a complete binary tree

Why are heaps often implemented using arrays

Because a heap is a complete binary tree, which can be more easily represented using an array than linked nodes

How is a heap used in a priority queue

Each node stores an element and its priority, and the heap is maintained so that higher-priority elements are closer to the root

What is the first step when adding an element to a heap

Place the new element in the first available location to maintain the complete binary tree structure

Why might adding an element break the heap property

Because the new element may have a higher priority than its parent

What is reheapification upward

The process of swapping a newly added element with its parent until it reaches a valid position

When does reheapification upward stop

When the element reaches the root or its parent has a higher or equal priority

What is the first step when removing an element from a heap

Remove the root element, which has the highest priority

What replaces the root after removal

The last element in the deepest level is moved to the root

Why is reheapification downward needed

Because moving the last element to the root may violate the heap property

What is reheapification downward

The process of swapping the out-of-place root with its higher-priority child until the heap property is restored

When does reheapification downward stop

When the element reaches a leaf or has children with lower or equal priority

What is a B-tree

A B-tree is a tree structure where nodes can have more than two children and store multiple elements

Why are B-trees used

They prevent trees from becoming unbalanced and keep leaf depth small

What is the MINIMUM constant in a B-tree

A positive integer that determines the minimum number of elements in each node (except possibly the root)

What is the maximum number of elements in a B-tree node

Twice the value of MINIMUM

How are elements stored in a B-tree node

In a partially filled array sorted from smallest to largest

How many children does a non-leaf B-tree node have

One more than the number of elements in the node

How are subtrees organized in a B-tree

Elements in each subtree are ordered relative to the node’s elements, ensuring proper search behavior

What ensures a B-tree is balanced

All leaves must have the same depth

How does searching in a B-tree work

Check the root, and if not found, recursively search the appropriate subtree based on element comparisons

What is loose addition in a B-tree

A method that allows temporarily exceeding the maximum number of elements in the root before fixing it

Why is loose addition useful

It simplifies insertion by delaying enforcement of strict B-tree rules

What is the worst-case time complexity for binary trees

O(n)
What is the worst-case time complexity for heaps and B-trees