Heap data structure
What is the Heap data structure?
Data structure The heap is a special case of a balanced binary tree data structure, where the root node's key is compared to its children and arranged accordingly. If α has a child node β then:
key (α) ≥ key (β)
When the value of the parent node is greater than the value of the child node, this attribute creates a Max Heap. Based on this criterion, a Heap can be one of two types:
With data filled in → 35 33 42 10 14 19 27 44 26 31
Min-Heap : here the value of the root node is less than or equal to the values of the child nodes.
Max-Heap : here the value of the root node is greater than or equal to the value of the child nodes.
The above two example trees are all built on the same input data and the same order.
Max Heap construction algorithm
We will use the same example to illustrate how to create a Max Heap. The method to build Min Heap is similar.
We will deduce an algorithm for Max Heap by inserting an element at a time. At any time, Heap must maintain (obey) its properties. During the insert process, we also assume that we are inserting a node in HEAPIFIED Tree.
Bước 1 : Tạo một nút mới tại vị trí cuối cùng của Heap. Bước 2 : Gán giá trị mới cho nút này. Bước 3 : So sánh giá trị của nút con với giá trị cha. Bước 4 : Nếu giá trị của cha là nhỏ hơn con thì tráo đổi chúng. Bước 5 : Lặp lại bước 3 và 4 cho tới khi vẫn duy trì thuộc tính của Heap.
Note : In the Min Heap build algorithm, the value of the parent node will be smaller than the value of the child nodes.
For more details on Max Heap construction algorithm, let's look at the animated illustration below.
The algorithm deletes in Max Heap
Delete operation in Max (or Min) Heap always takes place at the root node and to delete the Largest (or Smallest) value. You follow the algorithm and animation below to understand more about this algorithm.
Bước 1 : Xóa nút gốc. Bước 2 : Di chuyển phần tử cuối cùng có bậc thấp nhất lên nút gốc. Bước 3 : So sánh giá trị của nút con này với giá trị của cha. Bước 4 : Nếu giá trị của cha là nhỏ hơn của con thì tráo đổi chúng. Bước 5 : Lặp lại bước 3 và 4 cho tới khi vẫn duy trì thuộc tính của Heap.
According to Tutorialspoint
Previous article: Spanning Tree in data structure and algorithm
Next lesson: Basics of recursion
You should read it
May be interested
- How to implement a graph data structure in Golangcharts are one of the essential data structures that you must know as a programmer. let's learn how to create graph/graph data structures in golang !
- Concept of Buffer in Node.jsnet javascript is unicode encoded conveniently but not really good with binary data. when working with tcp streams or file systems, it is necessary to handle octal data streams. node.js provides buffer classes that allow raw data to be stored as an array of integers corresponding to external raw memory allocation v8 heap.
- Search algorithm by widththe breadth search algorithm (breadth first search - bfs for short) walks through a wide graph and uses a queue to memorize adjacent vertices to start the search when no peak is found. adjacent in any loop.
- How to Implement a Stack Data Structure in C++a stack is a basic data structure that is commonly used throughout computer science. for example, a stack is utilized by your web browser to remember the last few pages you were on. developers and programmers should be very familiar with...
- What is Silo Structure? Advantages and disadvantages of silos and effective alternativeseveryone knows that a properly structured website is good for both users and seo. silo structure is one of many ways that seo experts recommend people to apply for their website.
- Deep search algorithmdeep search algorithms (depth first search - dfs for short), also called depth-first search algorithms, are algorithms that browse or search on a tree or graph and use the stack ( stack) to remember adjacent vertices to start the search when the adjacent vertex is not encountered in any loop.
- Environment settings in Data structuresbecause c and c ++ languages are the languages that almost every university uses to teach, in this chapter i will guide you to install c and c ++ to run the examples in the configuration series. structure and algorithm.
- What is URL? Structure of the URLwhat exactly is a url, what is its structure and composition? this article will give you an overview of urls and its structure.
- New achievement: TSP chip structure can run 1 million billion operations per secondchips with the tsp structure of startup groq can perform up to 1 peta task per second, that is, 1,000,000,000,000,000 actions per second.
- Types of data center designit professionals always have to learn, apply new ways to design the data center structure to get efficiency, ensure large capacity and easily expand without any trouble.