Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heaps and Heapsort - Coggle Diagram
Heaps and Heapsort
Heapsort
Heapsort:
• Introduction:
• Sorting algorithm using a binary heap data structure.
• Process:
• Build a heap from the unsorted data.
• Swap the root (maximum/minimum element) with the last element.
• Reduce the heap size and heapify the root.
• Repeat until the heap is empty.
• Efficiency:
• Time complexity: O(n log n) in the worst and average cases.
• In-place sorting.
Heaps
Notion of the Heap:
• Definition: A heap is a specialized binary tree-based data structure.
• Characteristics:
• Complete binary tree.
• Heap property: Parent nodes have values less/greater than their children (min-heap/max-heap).
Intro
6.4 Heaps and Heapsort:
Notion of the Heap:
• Definition: A heap is a binary tree-based data structure.
• Characteristics:
• Complete binary tree.
• Heap property: Parent nodes have values less/greater than their children (min-heap/max-heap).
Heapsort:
• Introduction:
• Sorting algorithm leveraging a binary heap.
• Process:
• Build a heap from unsorted data.
• Swap the root (max/min element) with the last element.
• Reduce heap size and heapify the root.
• Repeat until the heap is empty.
• Efficiency:
• Time complexity: O(n log n) in worst/average cases.
• In-place sorting.