Class Notes (839,242)
CPSC 319 (12)
Lecture 11

# CPSC 319 Lecture 11: 11 Heaps and Heapsort

4 Pages
67 Views

Department
Computer Science
Course Code
CPSC 319
Professor
Leonard Manzara

This preview shows page 1. Sign up to view the full 4 pages of the document.
Description
Heaps and Heapsort Heaps - A max heap is a binary tree where: o The value of each node is ≥ the values of its children o The tree is complete 268 ■ Chapter 6 Binary Trees § The tree is perfectly balanced o The leaf nodes in the last level are all pushed to the left o Height is < lg# o The largest element is always the root node FIGURE 6.51 Examples of (a) heaps and (b–c) nonheaps. o E.g. Drozdek p. 268 15 10 21 6 8 7 10 12 2 3 6 (a) - A min heap is similar except the value of each node is ≤ the values of its children o The root contains the smallest element 6 10 12 6 10 Section 6.9 Heaps ■ 269 - Heaps are not perfectly ordered o Order is maintained only through linear lines of descent 15 2 7 10 21 15 8 7 o Lateral lines may be out of order 8 3 FIGUo E.g. Drozdek p. 269 nt heaps construct2d wit3 the same el6ments. (b) Different heaps constructed with the same(c)ements: 10 10 10 2 9 9 8 7 9 FIGURE 6.52 The array [2 8 6 1 10 15 3 12 11] seen as a tree. 1 0 8 7 7 2 0 1 0 1 2 8 (a) (b) (c) - Heaps are normally implemented using2arrays (or vectors) - Elements are stored sequentially in the array: 8 6 o Level by levenode. But the relation between sibling nodes or, to continue the kinship terminology, o From left to right at each level betwee1 uncl10and n15hew n3des is not determined. The order of the elements obeys - The root node is alwa linear line of descent, disregarding lateral.or this reason, lal the trees in Figure - The position of the left child of a node at ! is: 2! + 1, where the position is < # best. - The position of the right child of a node is 2! + 2, where the position is < # - The position of the parent of a node at ! is: (! − 1)/2, where 1 ≤ ! < # o Note: assumesA heap is an excellent way to implement a priority queue.Section 4.3 used linked lists placed at sequential locato implement priority queues, structures for which the complexity was expressed in level from left to right.terms ofO(n) or O(▯n ▯).For large n, this may be too ineffective.On the other hand,a with no gaps.Now,a heap can be defined as an arrayheap of length n in which heap is a perfectly balanced tree; hence,reaching a leaf requiresO(lg n) searches.This heap[i] ≥ heap[2 · i + 1]y prom,for0.≤ i
More Less

Only page 1 are available for preview. Some parts have been intentionally blurred.

Unlock Document

Unlock to view full version

Unlock Document
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.