Heap: Difference between revisions
| Line 23: | Line 23: | ||
Also see: {{Internal|Data_Structures#DELETE|Data Structures | <tt>DELETE</tt>}} | Also see: {{Internal|Data_Structures#DELETE|Data Structures | <tt>DELETE</tt>}} | ||
===Min Heap and Max Heap=== | ===Min Heap and Max Heap=== | ||
A heap is constructed in such a way that it maintains a minimum value or a maximum value, but not both. A heap that maintains the minimum value is called a '''min heap'''. A heap that maintains the maximum value is called a '''max heap'''. | A heap is constructed in such a way that it maintains a minimum value or a maximum value, but not both. A heap that maintains the minimum value is called a '''min heap'''. A heap that maintains the maximum value is called a '''max heap'''. If both extracting minimum and maximum are required, use a [[Tree_Concepts#Binary_Search_Tree|binary search tree]] instead. | ||
Revision as of 21:56, 9 October 2021
External
Internal
Overview
This article is about binary heaps. A binary heap data structure is an array where data is placed to form a complete binary tree, plus the index of the last node in the heap. Each element of the array contains a pointer to tree nodes. Each node contains at least a key. The heap works by comparing key and placing the pointer of the associated nodes in the right position in the heap. Duplicate key values are supported.
More details CLRS page 151, page 1177.
Supported Operations
INSERT
Insert a node in the tree.
Also see:
REMOVE-MIN
Remove the node from the heap with minimum key value.
Also see:
Min Heap and Max Heap
A heap is constructed in such a way that it maintains a minimum value or a maximum value, but not both. A heap that maintains the minimum value is called a min heap. A heap that maintains the maximum value is called a max heap. If both extracting minimum and maximum are required, use a binary search tree instead.