Book Image

C# Data Structures and Algorithms

By : Marcin Jamro
Book Image

C# Data Structures and Algorithms

By: Marcin Jamro

Overview of this book

Data structures allow organizing data efficiently. They are critical to various problems and their suitable implementation can provide a complete solution that acts like reusable code. In this book, you will learn how to use various data structures while developing in the C# language as well as how to implement some of the most common algorithms used with such data structures. At the beginning, you will get to know arrays, lists, dictionaries, and sets together with real-world examples of your application. Then, you will learn how to create and use stacks and queues. In the following part of the book, the more complex data structures will be introduced, namely trees and graphs, together with some algorithms for searching the shortest path in a graph. We will also discuss how to organize the code in a manageable, consistent, and extendable way. By the end of the book,you will learn how to build components that are easy to understand, debug, and use in different applications.
Table of Contents (14 chapters)

Binary heaps

A heap is another variant of a tree, which exists in two versions: min-heap and max-heap. For each of them, an additional property must be satisfied:

  • For min-heap: The value of each node must be greater than or equal to the value of its parent node
  • For max-heap: The value of each node must be less than or equal to the value of its parent node

These rules perform a very important role, because they dictate that the root node always contains the smallest (in the min-heap) or the largest (in the max-heap) value. For this reason, it is a convenient data structure for implementing a priority queue, described in Chapter 3, Stacks and Queues.

Heaps come in many variants, including binary heaps, which are the topic of this section. In this case, a heap must comply to one of the previously-mentioned rules (depending on the kind: min-heap or max-heap) and it must adhere to the complete binary tree rule, which requires that each node cannot contain more than two children, as well as all levels...