Programming abecas notes fourteen piles

This famous quote: “Let the coral from the erosion of stormy waves? That would ruin their beauty.”

Welcome to reprint, reprint please indicate the source: blog.csdn.net/notbaron/ar…

The use of heap is primarily used to solve two problems: sorting and priority queuing.

A heap is a data structure used to represent a collection of elements. In fact, the elements in a pair can be of any ordered type.

The author introduces the binary tree, and then introduces the two functions that can be adjusted after inserting the value into the binary tree to break the binary tree properties. They’re called siftup and siftdown. If the decimal is on a node, siftup must be used to float that number up. Similarly, the tree must be on a leaf node. If it is on a root, siftdown must be called to sink it down.

1. Priority queue

A data structure is viewed from two sides: externally it shows what it does and internally it shows what it can do.

Priority queues operate on a set of elements initialized to empty, insert a new element into the set, and delete the smallest element in the set. Priority queues can be implemented through sequential structures such as arrays, linked lists, etc.

The running time of the comparison algorithm is as follows:

Figure 1

\

Heap usage requires additional memory.

2. A sort

In this sorting method, only one array is used. The first stage builds the heap, and then pairs are used to build ordered sequences. Although heap sort guarantees zero (nlogn) performance in the worst case, we still find quicksort to be more useful in practice. The details are not described here.