Lectures: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29]

COMP2100
Lecture 11: Data Structures IV

Summary

This lecture covers basic material about tree traversals using explicit stacks (preorder) and queues (breadth-first search), then, using Huffman codes and Huffman trees as motivation, introduces priority queues and shows how they can be implemented as heaps, and, in turn, how heaps can be implemented as left-justified complete binary trees stored in arrays. As a special treat, we see how heaps are used in the classic sorting algorithm known as Heapsort.

This material was based on lectures from COMP1110 as well as sections 6.4 and 8.1-8.4 of Jeffrey H. Kingston, Algorithms and Data Structures: Design, Correctness, Analysis, second edition, Addison-Wesley, 1997.

You can download Lecture 11 as a PDF file.

Lectures: [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29]