## Data Structure Name: Heap - #### Description: - A special type of [[Binary Tree]] that must meet the following criteria: - Is a complete binary tree - The value of each node must be no greater than (or no less than) the value of its child nodes - #### Variations: - Min Heap - Max Heap - #### Diagram: - #### General Use: - Allows for accessing the largest or smallest data in a dataset efficiently ## Key Considerations - #### Properties: - #### Implementation Details: - To Insert: - Min Heap - Insert in binary right to maintain complete binary tree, move left if needed - If lower then parent, exchange nodes - If lower than new parent, exhtange - Max Heap - Insert in binary right to maintain complete binary tree, move left if needed - If lower then parent, exchange nodes - If lower than new parent, exchange - To Delete: - Move bottom right element to the top of the heap - Switch locations with lowest / highest children until a valid min / max heap again | | [[Big O - Time Complexity]] | [[Big O - Space Complexity]] | | ---------------- | --------------------------- | ---------------------------- | | Insertion | O(log(n)) | | | Deletion | O(log(n)) | | | Select Min / Max | O(1) | | - #### General Tips - #### Special Properties ## Specific Use Cases - TBD