2. Trees, Heaps, and Graphs | C++ Data Structures and Algorithm Design Principles

Sign In Start Free Trial

Book Overview & Buying
Table Of Contents

C++ Data Structures and Algorithm Design Principles

By : John Carey, Anil Achary, Shreyans Doshi , Payas Rajan

2.3 (4)

C++ Data Structures and Algorithm Design Principles

2.3 (4)

By: John Carey, Anil Achary, Shreyans Doshi , Payas Rajan

Overview of this book

C++ is a mature multi-paradigm programming language that enables you to write high-level code with a high degree of control over the hardware. Today, significant parts of software infrastructure, including databases, browsers, multimedia frameworks, and GUI toolkits, are written in C++. This book starts by introducing C++ data structures and how to store data using linked lists, arrays, stacks, and queues. In later chapters, the book explains the basic algorithm design paradigms, such as the greedy approach and the divide-and-conquer approach, which are used to solve a large variety of computational problems. Finally, you will learn the advanced technique of dynamic programming to develop optimized implementations of several algorithms discussed in the book. By the end of this book, you will have learned how to implement standard data structures and algorithms in efficient and scalable C++ 14 code.

Preface

Preface

About the Book

Free Chapter

1. Lists, Stacks, and Queues

1. Lists, Stacks, and Queues

Introduction

Contiguous Versus Linked Data Structures

std::array

std::vector

std::forward_list

Iterators

std::list

std::deque – Special Version of std::vector

Container Adaptors

Benchmarking

Summary

2. Trees, Heaps, and Graphs

2. Trees, Heaps, and Graphs

Introduction

Non-Linear Problems

Tree – It's Upside Down!

Variants of Trees

Heaps

Graphs

Summary

3. Hash Tables and Bloom Filters

3. Hash Tables and Bloom Filters

Introduction

Hash Tables

Collisions in Hash Tables

C++ Hash Tables

Bloom Filters

Summary

4. Divide and Conquer

4. Divide and Conquer

Introduction

Binary Search

Understanding the Divide-and-Conquer Approach

Sorting Using Divide and Conquer

C++ Standard Library Tools for Divide and Conquer

Dividing and Conquering at a Higher Abstraction Level – MapReduce

Summary

5. Greedy Algorithms

5. Greedy Algorithms

Introduction

Basic Greedy Algorithms

The Knapsack Problem(s)

The Vertex Coloring Problem

Summary

6. Graph Algorithms I

6. Graph Algorithms I

Introduction

The Graph Traversal Problem

Prim's MST Algorithm

Dijkstra's Shortest Path Algorithm

Summary

7. Graph Algorithms II

7. Graph Algorithms II

Introduction

Revisiting the Shortest Path Problem

The Bellman-Ford Algorithm

The Bellman-Ford Algorithm (Part II) – Negative Weight Cycles

Johnson's Algorithm

Strongly Connected Components

Kosaraju's Algorithm

Choosing the Right Approach

Summary

8. Dynamic Programming I

8. Dynamic Programming I

Introduction

What Is Dynamic Programming?

Memoization – The Top-Down Approach

Tabulation – the Bottom-Up Approach

Subset Sum Problem

Dynamic Programming on Strings and Sequences

Activity 21: Melodic Permutations

Summary

9. Dynamic Programming II

9. Dynamic Programming II

Introduction

An Overview of P versus NP

Reconsidering the Subset Sum Problem

The Knapsack Problem

Graphs and Dynamic Programming

Summary

Appendix

Appendix

Chapter 1: Lists, Stacks, and Queues

Chapter 2: Trees, Heaps, and Graphs

Chapter 3: Hash Tables and Bloom Filters

Chapter 4: Divide and Conquer

Chapter 5: Greedy Algorithms

Chapter 6: Graph Algorithms I

Chapter 7: Graph Algorithms II

Chapter 8: Dynamic Programming I

Chapter 9: Dynamic Programming II

Tree – It's Upside Down!

As we discussed in the previous section, a tree is nothing but some objects or nodes connected to other nodes via a relationship that results in some sort of hierarchy. If we were to show this hierarchy in a graphical way, it would look like a tree, while the different edges would look like its branches. The main node, which is not dependent on any other node, is also known as a root node and is usually represented at the top. So, unlike an actual tree, this tree is upside down, with the root at its top!

Let's try to construct a structure for a very basic version of an organizational hierarchy.

Exercise 7: Creating an Organizational Structure

In this exercise, we will implement a basic version of the organizational tree we saw in the introduction to this chapter. Let's get started:

First, let's include the required headers:
#include <iostream>
#include <queue>
For simplicity, we'll assume that any person can have, at...

CONTINUE READING

83

Tech Concepts

36

Programming languages

73

Tech Tools

Unlimited access to the largest independent learning library in tech of over 8,000 expert-authored tech books and videos.

Innovative learning tools, including AI book assistants, code context explainers, and text-to-speech.

50+ new titles added per month and exclusive early access to books as they are being written.

C++ Data Structures and Algorithm Design Principles

Search

Your notes and bookmarks