cp_library/ds/heap/heapsiftdown_fn.py

• View this file on GitHub
• Last update: 2025-08-24 20:27:05+09:00

Required by

• cp_library/alg/graph/csr/digraph_weighted_cls.py
• cp_library/alg/graph/csr/digraph_weighted_meta_cls.py
• cp_library/alg/graph/csr/graph_potential_cls.py
• cp_library/alg/graph/csr/graph_weighted_base_cls.py
• cp_library/alg/graph/csr/graph_weighted_cls.py
• cp_library/alg/graph/csr/graph_weighted_meta_cls.py
• cp_library/alg/tree/csr/aux_tree_base_cls.py
• cp_library/alg/tree/csr/aux_tree_cls.py
• cp_library/alg/tree/csr/aux_tree_weighted_cls.py
• cp_library/alg/tree/csr/hld_weighted_cls.py
• cp_library/alg/tree/csr/tree_weighted_base_cls.py
• cp_library/alg/tree/csr/tree_weighted_cls.py
• cp_library/alg/tree/csr/tree_weighted_meta_cls.py
• cp_library/ds/heap/heappush_fn.py
• cp_library/ds/heap/max_k_heap_cls.py
• cp_library/ds/heap/min_heap_cls.py
• cp_library/ds/heap/min_multiset_cls.py
• cp_library/ds/heap/priority_queue_cls.py
• perf/heap_csr.py
• perf/heap_view.py

Verified with

• test/aoj/grl/grl_1_a_fast_dijkstra.test.py
• test/aoj/grl/grl_1_a_graph_distance.test.py
• test/aoj/grl/grl_1_b_fast_bellman_ford.test.py
• test/aoj/grl/grl_1_c_fast_floyd_warshall.test.py
• test/aoj/grl/grl_2_a_graph_kruskal.test.py
• test/aoj/grl/grl_5_a_fast_diameter.test.py
• test/aoj/grl/grl_5_b_fast_height.test.py
• test/aoj/vol/0439_aux_dijkstra.test.py
• test/aoj/vol/0439_aux_rerooting_dp.test.py
• test/aoj/vol/0439_aux_weighted_rerooting_dp.test.py
• test/atcoder/abc/abc249_f_max_k_heap.test.py
• test/atcoder/abc/abc294_g_fast_tree_hld.test.py
• test/atcoder/abc/abc294_g_fast_tree_hld_bit.test.py
• test/atcoder/abc/abc294_g_fast_tree_lca_table_weighted_bit.test.py
• test/atcoder/abc/abc361_e_tree_diameter.test.py
• test/atcoder/abc/abc375_g_find_bridges.test.py
• test/library-checker/data-structure/double_ended_priority_queue_2heaps_fast_heapq.test.py
• test/library-checker/graph/minimum_spanning_tree_kruskal.test.py
• test/library-checker/graph/minimum_spanning_tree_kruskal_heap.test.py
• test/library-checker/graph/shortest_path_fast_graph.test.py
• test/library-checker/graph/shortest_path_min_heap.test.py
• test/library-checker/tree/tree_diameter.test.py
• test/library-checker/tree/tree_path_composite_sum.test.py
• test/yukicoder/3407.test.py

Code

import cp_library.__header__
import cp_library.ds.__header__
import cp_library.ds.heap.__header__

def heapsiftdown(heap: list, root: int, pos: int):
    item = heap[pos]
    while root < pos and item < heap[p := (pos-1)>>1]: heap[pos], pos = heap[p], p
    heap[pos] = item

'''
╺━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╸
             https://kobejean.github.io/cp-library               
'''



def heapsiftdown(heap: list, root: int, pos: int):
    item = heap[pos]
    while root < pos and item < heap[p := (pos-1)>>1]: heap[pos], pos = heap[p], p
    heap[pos] = item

Back to top page