6.1 Heaps - CLRS Solutions

Home » Where In A Max-heap Might The Smallest Element Reside » 6.1 Heaps - CLRS Solutions

Maybe your like

Skip to content CLRS Solutions walkccc/CLRS
  • Preface
  • I Foundations I Foundations
    • 1 The Role of Algorithms in Computing 1 The Role of Algorithms in Computing
      • 1.1 Algorithms
      • 1.2 Algorithms as a technology
      • Chap 1 Problems Chap 1 Problems
        • Problem 1-1
    • 2 Getting Started 2 Getting Started
      • 2.1 Insertion sort
      • 2.2 Analyzing algorithms
      • 2.3 Designing algorithms
      • Chap 2 Problems Chap 2 Problems
        • 2-1 Insertion sort on small arrays in merge sort
        • 2-2 Correctness of bubblesort
        • 2-3 Correctness of Horner's rule
        • 2-4 Inversions
    • 3 Growth of Functions 3 Growth of Functions
      • 3.1 Asymptotic notation
      • 3.2 Standard notations and common functions
      • Chap 3 Problems Chap 3 Problems
        • 3-1 Asymptotic behavior of polynomials
        • 3-2 Relative asymptotic growths
        • 3-3 Ordering by asymptotic growth rates
        • 3-4 Asymptotic notation properties
        • 3-5 Variations on $O$ and $\Omega$
        • 3-6 Iterated functions
    • 4 Divide-and-Conquer 4 Divide-and-Conquer
      • 4.1 The maximum-subarray problem
      • 4.2 Strassen's algorithm for matrix multiplication
      • 4.3 The substitution method for solving recurrences
      • 4.4 The recursion-tree method for solving recurrences
      • 4.5 The master method for solving recurrences
      • 4.6 Proof of the master theorem
      • Chap 4 Problems Chap 4 Problems
        • 4-1 Recurrence examples
        • 4-2 Parameter-passing costs
        • 4-3 More recurrence examples
        • 4-4 Fibonacci numbers
        • 4-5 Chip testing
        • 4-6 Monge arrays
    • 5 Probabilistic Analysis and Randomized Algorithms 5 Probabilistic Analysis and Randomized Algorithms
      • 5.1 The hiring problem
      • 5.2 Indicator random variables
      • 5.3 Randomized algorithms
      • 5.4 Probabilistic analysis and further uses of indicator random variables
      • Chap 5 Problems Chap 5 Problems
        • 5-1 Probabilstic counting
        • 5-2 Searching an unsorted array
  • II Sorting and Order Statistics II Sorting and Order Statistics
    • 6 Heapsort 6 Heapsort
      • 6.1 Heaps 6.1 Heaps Table of contents
        • 6.1-1
        • 6.1-2
        • 6.1-3
        • 6.1-4
        • 6.1-5
        • 6.1-6
        • 6.1-7
      • 6.2 Maintaining the heap property
      • 6.3 Building a heap
      • 6.4 The heapsort algorithm
      • 6.5 Priority queues
      • Chap 6 Problems Chap 6 Problems
        • 6-1 Building a heap using insertion
        • 6-2 Analysis of $d$-ary heaps
        • 6-3 Young tableaus
    • 7 Quicksort 7 Quicksort
      • 7.1 Description of quicksort
      • 7.2 Performance of quicksort
      • 7.3 A randomized version of quicksort
      • 7.4 Analysis of quicksort
      • Chap 7 Problems Chap 7 Problems
        • 7-1 Hoare partition correctness
        • 7-2 Quicksort with equal element values
        • 7-3 Alternative quicksort analysis
        • 7-4 Stack depth for quicksort
        • 7-5 Median-of-3 partition
        • 7-6 Fuzzy sorting of intervals
    • 8 Sorting in Linear Time 8 Sorting in Linear Time
      • 8.1 Lower bounds for sorting
      • 8.2 Counting sort
      • 8.3 Radix sort
      • 8.4 Bucket sort
      • Chap 8 Problems Chap 8 Problems
        • 8-1 Probabilistic lower bounds on comparison sorting
        • 8-2 Sorting in place in linear time
        • 8-3 Sorting variable-length items
        • 8-4 Water jugs
        • 8-5 Average sorting
        • 8-6 Lower bound on merging sorted lists
        • 8-7 The $0$-$1$ sorting lemma and columnsort
    • 9 Medians and Order Statistics 9 Medians and Order Statistics
      • 9.1 Minimum and maximum
      • 9.2 Selection in expected linear time
      • 9.3 Selection in worst-case linear time
      • Chap 9 Problems Chap 9 Problems
        • 9-1 Largest $i$ numbers in sorted order
        • 9-2 Weighted median
        • 9-3 Small order statistics
        • 9-4 Alternative analysis of randomized selection
  • III Data Structures III Data Structures
    • 10 Elementary Data Structures 10 Elementary Data Structures
      • 10.1 Stacks and queues
      • 10.2 Linked lists
      • 10.3 Implementing pointers and objects
      • 10.4 Representing rooted trees
      • Chap 10 Problems Chap 10 Problems
        • 10-1 Comparisons among lists
        • 10-2 Mergeable heaps using linked lists
        • 10-3 Searching a sorted compact list
    • 11 Hash Tables 11 Hash Tables
      • 11.1 Direct-address tables
      • 11.2 Hash tables
      • 11.3 Hash functions
      • 11.4 Open addressing
      • 11.5 Perfect hashing
      • Chap 11 Problems Chap 11 Problems
        • 11-1 Longest-probe bound for hashing
        • 11-2 Slot-size bound for chaining
        • 11-3 Quadratic probing
        • 11-4 Hashing and authentication
    • 12 Binary Search Trees 12 Binary Search Trees
      • 12.1 What is a binary search tree?
      • 12.2 Querying a binary search tree
      • 12.3 Insertion and deletion
      • 12.4 Randomly built binary search trees
      • Chap 12 Problems Chap 12 Problems
        • 12-1 Binary search trees with equal keys
        • 12-2 Radix trees
        • 12-3 Average node depth in a randomly built binary search tree
        • 12-4 Number of different binary trees
    • 13 Red-Black Trees 13 Red-Black Trees
      • 13.1 Properties of red-black trees
      • 13.2 Rotations
      • 13.3 Insertion
      • 13.4 Deletion
      • Chap 13 Problems Chap 13 Problems
        • 13-1 Persistent dynamic sets
        • 13-2 Join operation on red-black trees
        • 13-3 AVL trees
        • 13-4 Treaps
    • 14 Augmenting Data Structures 14 Augmenting Data Structures
      • 14.1 Dynamic order statistics
      • 14.2 How to augment a data structure
      • 14.3 Interval trees
      • Chap 14 Problems Chap 14 Problems
        • 14-1 Point of maximum overlap
        • 14-2 Josephus permutation
  • IV Advanced Design and Analysis Techniques IV Advanced Design and Analysis Techniques
    • 15 Dynamic Programming 15 Dynamic Programming
      • 15.1 Rod cutting
      • 15.2 Matrix-chain multiplication
      • 15.3 Elements of dynamic programming
      • 15.4 Longest common subsequence
      • 15.5 Optimal binary search trees
      • Chap 15 Problems Chap 15 Problems
        • 15-1 Longest simple path in a directed acyclic graph
        • 15-2 Longest palindrome subsequence
        • 15-3 Bitonic euclidean
        • 15-4 Printing neatly
        • 15-5 Edit distance
        • 15-6 Planning a company party
        • 15-7 Viterbi algorithm
        • 15-8 Image compression by seam carving
        • 15-9 Breaking a string
        • 15-10 Planning an investment strategy
        • 15-11 Inventory planning
        • 15-12 Signing free-agent baseball players
    • 16 Greedy Algorithms 16 Greedy Algorithms
      • 16.1 An activity-selection problem
      • 16.2 Elements of the greedy strategy
      • 16.3 Huffman codes
      • 16.4 Matroids and greedy methods
      • 16.5 A task-scheduling problem as a matroid
      • Chap 16 Problems Chap 16 Problems
        • 16-1 Coin changing
        • 16-2 Scheduling to minimize average completion time
        • 16-3 Acyclic subgraphs
        • 16-4 Scheduling variations
        • 16-5 Off-line caching
    • 17 Amortized Analysis 17 Amortized Analysis
      • 17.1 Aggregate analysis
      • 17.2 The accounting method
      • 17.3 The potential method
      • 17.4 Dynamic tables
      • Chap 17 Problems Chap 17 Problems
        • 17-1 Bit-reversed binary counter
        • 17-2 Making binary search dynamic
        • 17-3 Amortized weight-balanced trees
        • 17-4 The cost of restructuring red-black trees
        • 17-5 Competitive analysis of self-organizing lists with move-to-front
  • V Advanced Data Structures V Advanced Data Structures
    • 18 B-Trees 18 B-Trees
      • 18.1 Definition of B-trees
      • 18.2 Basic operations on B-trees
      • 18.3 Deleting a key from a B-tree
      • Chap 18 Problems Chap 18 Problems
        • 18-1 Stacks on secondary storage
        • 18-2 Joining and splitting 2-3-4 trees
    • 19 Fibonacci Heaps 19 Fibonacci Heaps
      • 19.1 Structure of Fibonacci heaps
      • 19.2 Mergeable-heap operations
      • 19.3 Decreasing a key and deleting a node
      • 19.4 Bounding the maximum degree
      • Chap 19 Problems Chap 19 Problems
        • 19-1 Alternative implementation of deletion
        • 19-2 Binomial trees and binomial heaps
        • 19-3 More Fibonacci-heap operations
        • 19-4 2-3-4 heaps
    • 20 van Emde Boas Trees 20 van Emde Boas Trees
      • 20.1 Preliminary approaches
      • 20.2 A recursive structure
      • 20.3 The van Emde Boas tree
      • Chap 20 Problems Chap 20 Problems
        • 20-1 Space requirements for van Emde Boas trees
        • 20-2 $y$-fast tries
    • 21 Data Structures for Disjoint Sets 21 Data Structures for Disjoint Sets
      • 21.1 Disjoint-set operations
      • 21.2 Linked-list representation of disjoint sets
      • 21.3 Disjoint-set forests
      • 21.4 Analysis of union by rank with path compression
      • Chap 21 Problems Chap 21 Problems
        • 21-1 Off-line minimum
        • 21-2 Depth determination
        • 21-3 Tarjan's off-line least-common-ancestors algorithm
  • VI Graph Algorithms VI Graph Algorithms
    • 22 Elementary Graph Algorithms 22 Elementary Graph Algorithms
      • 22.1 Representations of graphs
      • 22.2 Breadth-first search
      • 22.3 Depth-first search
      • 22.4 Topological sort
      • 22.5 Strongly connected components
      • Chap 22 Problems Chap 22 Problems
        • 22-1 Classifying edges by breadth-first search
        • 22-2 Articulation points, bridges, and biconnected components
        • 22-3 Euler tour
        • 22-4 Reachability
    • 23 Minimum Spanning Trees 23 Minimum Spanning Trees
      • 23.1 Growing a minimum spanning tree
      • 23.2 The algorithms of Kruskal and Prim
      • Chap 23 Problems Chap 23 Problems
        • 23-1 Second-best minimum spanning tree
        • 23-2 Minimum spanning tree in sparse graphs
        • 23-3 Bottleneck spanning tree
        • 23-4 Alternative minimum-spanning-tree algorithms
    • 24 Single-Source Shortest Paths 24 Single-Source Shortest Paths
      • 24.1 The Bellman-Ford algorithm
      • 24.2 Single-source shortest paths in directed acyclic graphs
      • 24.3 Dijkstra's algorithm
      • 24.4 Difference constraints and shortest paths
      • 24.5 Proofs of shortest-paths properties
      • Chap 24 Problems Chap 24 Problems
        • 24-1 Yen's improvement to Bellman-Ford
        • 24-2 Nesting boxes
        • 24-3 Arbitrage
        • 24-4 Gabow's scaling algorithm for single-source shortest paths
        • 24-5 Karp's minimum mean-weight cycle algorithm
        • 24-6 Bitonic shortest paths
    • 25 All-Pairs Shortest Paths 25 All-Pairs Shortest Paths
      • 25.1 Shortest paths and matrix multiplication
      • 25.2 The Floyd-Warshall algorithm
      • 25.3 Johnson's algorithm for sparse graphs
      • Chap 25 Problems Chap 25 Problems
        • 25-1 Transitive closure of a dynamic graph
        • 25-2 Shortest paths in epsilon-dense graphs
    • 26 Maximum Flow 26 Maximum Flow
      • 26.1 Flow networks
      • 26.2 The Ford-Fulkerson method
      • 26.3 Maximum bipartite matching
      • 26.4 Push-relabel algorithms
      • 26.5 The relabel-to-front algorithm
      • Chap 26 Problems Chap 26 Problems
        • 26-1 Escape problem
        • 26-2 Minimum path cover
        • 26-3 Algorithmic consulting
        • 26-4 Updating maximum flow
        • 26-5 Maximum flow by scaling
        • 26-6 The Hopcroft-Karp bipartite matching algorithm
  • VII Selected Topics VII Selected Topics
    • 27 Multithreaded Algorithms 27 Multithreaded Algorithms
      • 27.1 The basics of dynamic multithreading
      • 27.2 Multithreaded matrix multiplication
      • 27.3 Multithreaded merge sort
      • Chap 27 Problems Chap 27 Problems
        • 27-1 Implementing parallel loops using nested parallelism
        • 27-2 Saving temporary space in matrix multiplication
        • 27-3 Multithreaded matrix algorithms
        • 27-4 Multithreading reductions and prefix computations
        • 27-5 Multithreading a simple stencil calculation
        • 27-6 Randomized multithreaded algorithms
    • 28 Matrix Operations 28 Matrix Operations
      • 28.1 Solving systems of linear equations
      • 28.2 Inverting matrices
      • 28.3 Symmetric positive-definite matrices and least-squares approximation
      • Chap 28 Problems Chap 28 Problems
        • 28-1 Tridiagonal systems of linear equations
        • 28-2 Splines
    • 29 Linear Programming 29 Linear Programming
      • 29.1 Standard and slack forms
      • 29.2 Formulating problems as linear programs
      • 29.3 The simplex algorithm
      • 29.4 Duality
      • 29.5 The initial basic feasible solution
      • Chap 29 Problems Chap 29 Problems
        • 29-1 Linear-inequality feasibility
        • 29-2 Complementary slackness
        • 29-3 Integer linear programming
        • 29-4 Farkas'ss lemma
        • 29-5 Minimum-cost circulation
    • 30 Polynomials and the FFT 30 Polynomials and the FFT
      • 30.1 Representing polynomials
      • 30.2 The DFT and FFT
      • 30.3 Efficient FFT implementations
      • Chap 30 Problems Chap 30 Problems
        • 30-1 Divide-and-conquer multiplication
        • 30-2 Toeplitz matrices
        • 30-3 Multidimensional fast Fourier transform
        • 30-4 Evaluating all derivatives of a polynomial at a point
        • 30-5 Polynomial evaluation at multiple points
        • 30-6 FFT using modular arithmetic
    • 31 Number-Theoretic Algorithms 31 Number-Theoretic Algorithms
      • 31.1 Elementary number-theoretic notions
      • 31.2 Greatest common divisor
      • 31.3 Modular arithmetic
      • 31.4 Solving modular linear equations
      • 31.5 The Chinese remainder theorem
      • 31.6 Powers of an element
      • 31.7 The RSA public-key cryptosystem
      • 31.8 Primality testing
      • 31.9 Integer factorization
      • Chap 31 Problems Chap 31 Problems
        • 31-1 Binary gcd algorithm
        • 31-2 Analysis of bit operations in Euclid's algorithm
        • 31-3 Three algorithms for Fibonacci numbers
        • 31-4 Quadratic residues
    • 32 String Matching 32 String Matching
      • 32.1 The naive string-matching algorithm
      • 32.2 The Rabin-Karp algorithm
      • 32.3 String matching with finite automata
      • 32.4 The Knuth-Morris-Pratt algorithm
      • Chap 32 Problems Chap 32 Problems
        • 32-1 String matching based on repetition factors
    • 33 Computational Geometry 33 Computational Geometry
      • 33.1 Line-segment properties
      • 33.2 Determining whether any pair of segments intersects
      • 33.3 Finding the convex hull
      • 33.4 Finding the closest pair of points
      • Chap 33 Problems Chap 33 Problems
        • 33-1 Convex layers
        • 33-2 Maximal layers
        • 33-3 Ghostbusters and ghosts
        • 33-4 Picking up sticks
        • 33-5 Sparse-hulled distributions
    • 34 NP-Completeness 34 NP-Completeness
      • 34.1 Polynomial time
      • 34.2 Polynomial-time verification
      • 34.3 NP-completeness and reducibility
      • 34.4 NP-completeness proofs
      • 34.5 NP-complete problems
      • Chap 34 Problems Chap 34 Problems
        • 34-1 Independent set
        • 34-2 Bonnie and Clyde
        • 34-3 Graph coloring
        • 34-4 Scheduling with profits and deadlines
    • 35 Approximation Algorithms 35 Approximation Algorithms
      • 35.1 The vertex-cover problem
      • 35.2 The traveling-salesman problem
      • 35.3 The set-covering problem
      • 35.4 Randomization and linear programming
      • 35.5 The subset-sum problem
      • Chap 35 Problems Chap 35 Problems
        • 35-1 Bin packing
        • 35-2 Approximating the size of a maximum clique
        • 35-3 Weighted set-covering problem
        • 35-4 Maximum matching
        • 35-5 Parallel machine scheduling
        • 35-6 Approximating a maximum spanning tree
        • 35-7 An approximation algorithm for the 0-1 knapsack problem
Table of contents
  • 6.1-1
  • 6.1-2
  • 6.1-3
  • 6.1-4
  • 6.1-5
  • 6.1-6
  • 6.1-7
6.1 Heaps

6.1-1¶

What are the minimum and maximum numbers of elements in a heap of height $h$?

At least $2^h$ and at most $2^{h + 1} − 1$. Can be seen because a complete binary tree of depth $h − 1$ has $\sum_{i = 0}^{h - 1} 2^i = 2^h - 1$ elements, and the number of elements in a heap of depth $h$ is between the number for a complete binary tree of depth $h − 1$ exclusive and the number in a complete binary tree of depth $h$ inclusive.

6.1-2¶

Show that an $n$-element heap has height $\lfloor \lg n \rfloor$.

Write $n = 2^m − 1 + k$ where $m$ is as large as possible. Then the heap consists of a complete binary tree of height $m − 1$, along with $k$ additional leaves along the bottom. The height of the root is the length of the longest simple path to one of these $k$ leaves, which must have length $m$. It is clear from the way we defined $m$ that $m = \lfloor \lg n\rfloor$.

6.1-3¶

Show that in any subtree of a max-heap, the root of the subtree contains the largest value occuring anywhere in the subtree.

If the largest element in the subtree were somewhere other than the root, it has a parent that is in the subtree. So, it is larger than it's parent, so, the heap property is violated at the parent of the maximum element in the subtree.

6.1-4¶

Where in a max-heap might the smallest element reside, assuming that all elements are distinct?

In any of the leaves, that is, elements with index $\lfloor n / 2 \rfloor + k$, where $k \geq 1$ (see exercise 6.1-7), that is, in the second half of the heap array.

6.1-5¶

Is an array that is in sorted order a min-heap?

Yes. For any index $i$, both $\text{LEFT}(i)$ and $\text{RIGHT}(i)$ are larger and thus the elements indexed by them are greater or equal to $A[i]$ (because the array is sorted.)

6.1-6¶

Is the array with values $\langle 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 \rangle$ a max-heap?

No. Since $\text{PARENT}(7)$ is $6$ in the array. This violates the max-heap property.

6.1-7¶

Show that, with the array representation for sorting an $n$-element heap, the leaves are the nodes indexed by $\lfloor n / 2 \rfloor + 1, \lfloor n / 2 \rfloor + 2, \ldots, n$.

Let's take the left child of the node indexed by $\lfloor n / 2 \rfloor + 1$.

$$ \begin{aligned} \text{LEFT}(\lfloor n / 2 \rfloor + 1) & = 2(\lfloor n / 2 \rfloor + 1) \\ & > 2(n / 2 - 1) + 2 \\ & = n - 2 + 2 \\ & = n. \end{aligned} $$

Since the index of the left child is larger than the number of elements in the heap, the node doesn't have childrens and thus is a leaf. Same goes for all nodes with larger indices.

Note that if we take element indexed by $\lfloor n / 2 \rfloor$, it will not be a leaf. In case of even number of nodes, it will have a left child with index $n$ and in the case of odd number of nodes, it will have a left child with index $n - 1$ and a right child with index $n$.

This makes the number of leaves in a heap of size $n$ equal to $\lceil n / 2 \rceil$.

Tag » Where In A Max-heap Might The Smallest Element Reside