Binary Heaps

These flashcards cover key concepts related to binary heaps and their properties as discussed in the lecture.

Heap

An Abstract Data Type that defines certain behaviors for a data structure.

Max Heap

A heap structure where all values in the subtree of a given node are less than or equal to the value of that node, with the root storing the highest value.

Min Heap

A heap structure where all values in the subtree of a given node are greater than or equal to the value of that node, with the root storing the smallest value.

Complete Binary Tree

A binary tree where all levels are fully filled except possibly the last, which is filled from left to right.

Priority Queue

A queue where the ordering of elements is based on priority rather than the order of arrival.

Percolate Up

A procedure in a max heap where a newly inserted node is swapped with its parent until the heap property is restored.

Heapification Upward

The process of maintaining the heap property by moving a value up in the structure to its correct position.

Delete Max

A function in a max heap that removes and returns the root node, which contains the maximum value.

Percolate Down

A procedure that maintains the heap property by moving a node down in the structure, swapping with its largest child.

Heap Sort

A sorting algorithm that builds a heap from a list of items, extracts the minimum item, and fixes the heap for all elements, resulting in O(n log n) time complexity.