Data Structures · topic
Binary heap array indexing, insertion and deletion with sift-up and sift-down traces, heap property checks, bottom-up build-heap in linear time, where the k-th smallest key can sit, counting heaps, and d-ary heaps.
The binary heap as a complete binary tree stored in an array: 1-based and 0-based index maps, leaf range and height, insertion with sift-up and delete-min with sift-down traced swap by swap, the heap property test (with the corrected inequality), where the maximum of a min-heap can be, and the cost of every heap operation. Every array and count is produced by a verification script.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
Bottom-up build-heap traced on GATE CS 2024 Set 1 Q.41, why it is linear (exact worst-case swap count), build-heap compared with repeated insertion, the depths where the k-th smallest key can sit (brute force over every heap on 10 and 12 keys), leaf positions (GATE CS 2024 Set 1 Q.43 and 2026 Set 1 Q.23), the number of distinct heaps on n keys, and d-ary heaps with their index maps, height and costs.
A partial preview of the top of the sheet. The full sheet is in the Data Structures cheat sheet pack.
