How does a heap differ from a fully sorted tree?

A heap constrains parent-child keys but does not order siblings or separate branches.

How does a priority queue differ from a heap?

A priority queue specifies behavior; a heap is a data structure that can implement it.

What makes a binary tree complete?

Every level is full except possibly the last, whose nodes are filled from left to right.

Moving a node toward the root while it violates the heap property with its parent.

What is the time complexity of bottom-up heapify?

$O(N)$ to build a binary heap from an array of $N$ items.

Data structures & algorithmsLesson 2 of 2 in the course Trees and hashing

Binary Heaps: Ordering, Array Operations, and Applications

5 flashcards · 5 quiz questions · 5 match pairs · 4 fill-in sentences · English

Save course

Lesson progress

0 / 5

Your progress is kept in this browser only.Sign up to save it

Summary

A heap is a tree-based data structure designed to make the highest- or lowest-priority item easy to access. This lesson introduces the heap property, max-heaps and min-heaps, and the ways heaps differ from fully sorted trees.

A heap is a tree in which every node is related to its parent according to a rule called the heap property. The top node, which has no parent, is the root.

All flashcards

How does a heap differ from a fully sorted tree?: A heap constrains parent-child keys but does not order siblings or separate branches.
How does a priority queue differ from a heap?: A priority queue specifies behavior; a heap is a data structure that can implement it.
What makes a binary tree complete?: Every level is full except possibly the last, whose nodes are filled from left to right.
What is sift-up?: Moving a node toward the root while it violates the heap property with its parent.
What is the time complexity of bottom-up heapify?: $O(N)$ to build a binary heap from an array of $N$ items.

Quiz questions

Which structure is required for a binary heap?Answer: A complete binary tree
In a zero-based binary heap array, what is the parent index of a non-root node at index $i$ ?Answer: $\lfloor(i-1)/2\rfloor$
When does sift-up move a node toward the root?Answer: When its key violates the heap property with its parent
What is the time complexity of bottom-up heapify for an array of $N$ items?Answer: $O(N)$
How can a min-heap support merging $k$ already-sorted streams?Answer: Store each stream's next item, repeatedly remove the minimum, and add its successor

Based on the Wikipedia article Heap (data structure), licensed CC BY-SA 4.0. Adapted into a summary, flashcards and quizzes.

All Data structures & algorithms lessons

Data structures & algorithmsBinary Search Trees: Ordering, Operations, Height, and Uses5 flashcards · 5 quiz questions · 4 gamesPlay free →Data structures & algorithmsMerge Sort: Algorithms, Complexity, Variants, and Applications5 flashcards · 5 quiz questions · 4 gamesPlay free →

Summary

All flashcards

Quiz questions

More in Data structures & algorithms