Heap and Priority Queue

Table of Contents

• 1. Introduction to Heap and Priority Queue
• 2. What are the applications of Heap and Priority Queue?
• 3. Heap in C++ standard library
• 4. Priority Queue in C++ standard library
  • 4.1. Minimum Priority Queue
• 5. The Applications of Priority Queues
• 6. References

1 Introduction to Heap and Priority Queue

A heap is a tree-based data structure that adheres to the heap property: in a max heap, any parent node's key (value) is greater than or equal to the keys of its children. Conversely, in a min heap, the key of a parent node is less than or equal to the keys of its children.

For more details, refer to Wikipedia: Heap (data structure).

A priority queue is an abstract data type similar to a regular queue or stack, where each element has an associated priority. Elements with higher priority are served before those with lower priority.

For more details, refer to Wikipedia: Priority queue.

Although they are conceptually different, priority queues are often referred to as heaps because they are commonly implemented using heaps.

The binary heap is a data structure that efficiently supports the basic priority queue operations. It allows O(1) performance for accessing the root, O(log n) for insertions and deletions, and O(n) for initially building the heap from a set of n elements.

Note that the time complexity to build a heap is O(n log n) using a top-down approach, whereas a bottom-up approach achieves O(n).

Monotonic Stack

Table of Contents

• 1. Introduction to monotonic stack
• 2. What can monotonically increasing stacks do?
  • 2.1. To find the previous less element of each element in a vector with O(n) time.
  • 2.2. To find the next less element of each element in a vector with O(n) time.
• 3. What can monotonically decreasing stacks do?
• 4. When are monotonic stacks used?
• 5. The applications of monotonic stacks
• 6. References

1 Introduction to monotonic stack

A monotonic stack is a stack whose elements are monotonically increasing or decreasing.

If we pop greater elements from the stack before pushing a new element, the stack will increase from bottom to top. If we pop lesser elements, the stack will decrease.

The typical paradigm for an increasing monotonic stack is like:

for (int i = 0; i < A.size(); i++) {
    while (!stk.empty() && stk.top() > A[i]) {
        stk.pop();
    }
    stk.push(A[i]);
}

2 What can monotonically increasing stacks do?

Monotonically increasing stacks can be used to solve a variety of algorithmic problems. One common use case is for finding the nearest greater element in an array. By maintaining a stack of elements in increasing order, we can quickly determine the next greater element for each element in the array. Monotonically increasing stacks can also be used for finding the maximum area of a histogram, as well as for solving problems related to dynamic programming and graph algorithms.

2.1 To find the previous less element of each element in a vector with O(n) time.

What is the previous less element of an element in a vector? Suppose there is a vector [3, 8, 9, 6], for each element 3, 8, 9, and 6:

• There is no previous less element for 3.
• The previous less element of 8 is 3.
• The previous less element of 9 is 8.
• The previous less element of 6 is 3.

USB Power Delivery EPR Test

Java Collection Framework basics

Introduction to Wi-Fi

Modern C++ features

Modern C++

Table of Contents

• 1. C++11
  • 1.1. nullptr
  • 1.2. Strongly typed enumeration
  • 1.3. Uniform initialization
  • 1.4. Ranged based for loop
  • 1.5. Array container
  • 1.6. constexpr
  • 1.7. Explicitly deleted and defaulted functions
  • 1.8. Delegating constructers
  • 1.9. Automatic type deduction and decltype
  • 1.10. Lambda functions
  • 1.11. Hash tables
  • 1.12. rvalue reference and move semantics
  • 1.13. Smart pointer
• 2. C++14
  • 2.1. Binary literals
  • 2.2. Digit separators
  • 2.3. Function return type deductions
  • 2.4. Generic lambdas
  • 2.5. Generalized lambda captures
  • 2.6. Variable templates
  • 2.7. Extended constexpr
• 3. C++17
  • 3.1. Nested namespaces
  • 3.2. Variable declaration in if and switch
  • 3.3. constexpr if statement
  • 3.4. Structured binding declarations
  • 3.5. Folding expressions
• 4. C++20
  • 4.1. Immediate functions
  • 4.2. Abbreviated function templates
  • 4.3. Lambda templates
  • 4.4. Modules
  • 4.5. Concepts
  • 4.6. Ranges
  • 4.7. Coroutines
• 5. references

In this article, I will provide a tutorial on features in modern C++ using very simple examples. The examples will be kept short for beginners to quickly grasp the features.

The complete list of features can be found in the following links: C++11, C++14, C++17, C++20. Please refer to these links for more information.

1 C++11

1.1 nullptr

Considering function overloading:

void fun(int);
void fun(char *);

Traditionally, NULL is often defined as 0. The issue arises with which function will foo(NULL) call?

Thus, C++11 introduces a new kerword, nullptr, as a distinghished null pointer consant.

#include <iostream>

void fun(char *p) {
        std::cout << "hi pointer" << std::endl;

}

void fun(int i) {
        std::cout << "hi integer" << std::endl;

}

int main()
{
        fun(0);       // Calls func(int)
        fun(nullptr); // Calls func(char*)
        //fun(NULL);  // This generates an error
        return 0;

}

1.2 Strongly typed enumeration

Enumerations in C++03 are effectively integers and do not have their own scope. It is possible to compare two enum values of different enumeration types.

#include <iostream>

int main()
{
        enum Animal {Cat, Dog, Elephant};
        enum Fish {Clam, Dolphin, Eel};

        Animal a = Dog;
        Fish f = Dolphin;

        if (a == f)
                std::cout << "Dog == Dolphin" << std::endl;
        else
                std::cout << "Dog != Dolphin" << std::endl;
        return 0;
}

C11 (C standard revision) features

C11 revision

Table of Contents

• 1. Overview
• 2. Multiple threading
• 3. Generic selection
• 4. Alignment facilities
• 5. Static assertions
• 6. Anonymous structs and unions
• 7. Other features
  • 7.1. quick_exit() function
  • 7.2. _Noreturn function specifier
  • 7.3. Bounds-checking functions
  • 7.4. Unicode support
  • 7.5. complex types
• 8. C17 / C18
• 9. C2x
• 10. References

1 Overview

C11 is the informal name for ISO/IEC 9899:2011, the current standard for the C language that was ratified by ISO in December 2011.

It standardizes many features for safer programming, such as removal of gets() function.

Additionally, C11 adds concurrency support, type-generic expressions, alignment-related facilities, static assertion, unicode support, floating-point characteristic macros, no-return functions, anonymous structures and unions, and various bound-checking and reentrancy functions.

The following examples demonstrating C11 features can be compiled with options such as

clang -std=c11 ex.c

2 Multiple threading

C11 standardized multi-threading support.

It introduces new headers threads.h and stdatomic.h, supporting multiple threads of execution:

• threads creation and management
• mutexes
• conditional variables
• atomic objects
• thread specific storage

STM32CubeIDE C++ the simplest example with cin and cout

Table of Contents

• 1. Create a new STM32 project
• 2. Start programming
• 3. references

Refer to STM32CubeIDE Input/Output on STM32 Nucleo Board in advance for basics.

1 Create a new STM32 project

In STM32CubeIDE, create a new STM32 project.

In Setup STM32 project window, select C++ for the Targeted Language.

STM32CubeIDE Input/Output on STM32 Nucleo Board

Table of Contents

• 1. STM32CubeIDE installation
• 2. Create a new STM32 project
• 3. Start programming
• 4. Run and debug
• 5. References

Step by step to use printf() and scanf() in STM32CubeIDE with Nucleo-L152RE board.

1 STM32CubeIDE installation

Refer to UM2563 - STM32CubeIDE installation guide.

2 Create a new STM32 project

In STM32CubeIDE menu, click File | New | STM32 Project.