Skip to Main Content
Mastering Algorithms with C
book

Mastering Algorithms with C

by Kyle Loudon
August 1999
Intermediate to advanced content levelIntermediate to advanced
560 pages
18h 57m
English
O'Reilly Media, Inc.
Content preview from Mastering Algorithms with C

Description of Heaps

A heap is a tree, usually a binary tree, in which each child node has a smaller value than its parent. Thus, the root node is the largest node in the tree. We may also choose to orient a heap so that each child node has a larger value than its parent. In this case, the root node is the smallest node. Trees like these are partially ordered because, although the nodes along every branch have a specific order to them, the nodes at one level are not necessarily ordered with respect to the nodes at another. A heap in which each child is smaller than its parent is top-heavy . This is because the largest node is on top (see Figure 10.1). A heap in which each child is larger than its parent is bottom-heavy .

Heaps are left-balanced (see Chapter 9), so as nodes are added, the tree grows level by level from left to right. A particularly good way to represent left-balanced binary trees, and therefore heaps, is to store nodes contiguously in an array in the order we would encounter them in a level traversal (see Chapter 9). Assuming a zero-indexed array, this means that the parent of each node at some position i in the array is located at position (i - 1)/2, where means to ignore the fractional part of (i - 1)/2. The left and right children of a node are located at positions 2i + 1 and 2i + 2. This organization is especially important for heaps because it allows us to locate a heap’s last node quickly: the last node is the rightmost node at the deepest level. This ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Introducing Algorithms in C: A Step by Step Guide to Algorithms in C

Luciano Manelli
Head First C

Head First C

David Griffiths, Dawn Griffiths

Publisher Resources

ISBN: 1565924533Supplemental ContentErrata Page