Please enable JavaScript.
Coggle requires JavaScript to display documents.
M10, Heapsort, Heap - Coggle Diagram
-
-
Heap
Basic Operations
Insertion
Algorithm: Insert the new element at the end of the tree, then "heapify" up (bubble up) to restore the heap property.
Time Complexity: O(log n), as the height of the tree is log n.
-
-
-
Properties
Complete Binary Tree: Heaps are always complete binary trees, meaning all levels are fully filled except possibly for the last level, which is filled from left to right.
Heap Property: For a max-heap, the key at each node is at least as large as the keys of its children. For a min-heap, the key at each node is at most as large as the keys of its children.
Applications
Priority Queues: Heaps are commonly used to implement priority queues, where elements are processed based on their priority.
Graph Algorithms: Used in algorithms like Dijkstra's shortest path algorithm and Prim's minimum spanning tree algorithm.