algorithms
About
GitHubGitHub
  • Introduction
    • Arrays
    • Kadane S Algorithm
    • Matrix Traversals
    • Prefix Sum
    • Sequences
    • Sliding Window
    • Sliding Window Template
    • String Manipulation
    • Subset Sum
    • Subsets
    • Two Pointers
    • Bidirectional Dictionary
    • Bloom Filter
    • Circular Deque
    • Circular Queue
    • Connected Components
    • D-ary Heap
    • Dynamic Arrays
    • Fibonacci Heap
    • Hashmaps
    • Heap Implementation
    • Indexed D ary Heap
    • Indexed Priority Queue
    • LFU Cache
    • LRU Cache
    • Linked LIst
    • Sparse Table
    • Binary Search
    • Interpolation Search
    • Binary Lifting
    • Binary Search Tree
    • Binary Tree
    • Segment Tree
    • Bit Manipulation
    • Brainteasers
    • Logic
    • Boyer Moore Voting Algorithm
    • Combinatorics
    • 0 1 Knapsack
    • Backtracking
    • Backtracking 1
    • Dynamic Programming
    • Dynamic Programming 1
    • Geometry
    • Graham Scan
    • Avl Trees
    • Bfs
    • Bellman Ford S Algorithm
    • Bridges Algorithm
    • Cycle Detection in Directed Graphs
    • Dfs
    • Dijkstra S Shortest Path Algorithm
    • Eulerian Path
    • Floyd Warshall's Algorithm
    • Floyd's Cycle Detection Algorithm
    • Graph Structures
    • Graph Theory
    • Graphs
    • Iterative Deepening Search (IDS)
    • Kruskal S Algorithm
    • Maze solving Algorithms
    • Prim S Algorithm
    • Strongly Connected Components
    • Topological Sort
    • Union Find
    • Greedy Algorithm
    • Hashing
    • Intersection of Intervals
    • Intervals
    • Range Queries
    • Linked List
    • Mathematics
    • Queue Simulation
    • Reservoir Sampling
    • Bucket Sort
    • Count Sort
    • Cyclic Sort
    • Heaps
    • Insertion Sort
    • K Problems
    • Merge Sort
    • Quick Select
    • Quick Sort
    • Radix Sort
    • Selection Sort
    • Sort
    • Kth Largest
    • Top K Problems
    • Maximum Frequency Stack
    • Minimum Queue
    • Minimum Stack (Optimized)
    • Monotonic Queue
    • Stacks
    • Knuth Morris Pratt (Kmp)
    • String Matching
    • Trie

On This Page

  • Optimizations
  • Optimized Complexity
Question? Give us feedback →Edit this page
Advanced-Data-StructuresIndexed D ary Heap

Indexed D-ary Heap

Implementation

Optimizations

Optimized Complexity

Time Complexity

Notice that the maximum height for n nodes is logknlog_knlogk​nBuilding the heap is still O(n)Swim: O(logkn)O(log_kn)O(logk​n)Sink: O(klogkn)O(klog_kn)O(klogk​n)Swim < Sink

Space Complexity

O(n)

Related

Heap-Implementation Indexed-D-ary-Heap Indexed-Priority-Queue-(IPQ)

Heap ImplementationIndexed Priority Queue
MIT 2024 © Nextra.