是最小堆功能 [英] Is Min Heap Function

问题描述

我想编写一个告诉我给定列表是否是最小堆的函数.

I want to write a function that tells me whether a given list is a min heap.

到目前为止我写的是什么

What I have written so far:

def is_min_heap(L):
    return _is_min_heap(L, 0)

def _is_min_heap(L, i):
    if 
         #base case
    else:
        return (L[i] < L[2*i+1] and _is_min_heap(L, 2*i+1)) and (L[i] < L[2*i+2] and _is_min_heap(L, 2*1+2))

我不确定基本情况应该是什么，我的递归调用是否正确?

I am not sure what the base case should be and is my recursive calls correct?

还如何控制索引最终不会超出范围?

Also how can you control that the indexes are not eventually out of range?

推荐答案

对于给定的i，您有三种不同的情况:您有两个孩子，在这种情况下，您需要检查两个孩子的堆属性，并且还要检查递归检查两个子树；或者您只剩下一个孩子，在这种情况下，您只需要检查那个孩子即可；或者您没有孩子，即i是一片叶子，它本身始终是一个有效的堆.

You have three different cases for a given i: Either you have two children, in which case you need to check the heap property for both children and also recursively check both subtrees; or you have just a left children, in which case you just have to check that one; or you have no children, i.e. i is a leaf, which is always a valid heap by itself.

您可以通过检查子项的索引是否仍在列表中来检查子项的存在.

You can check the existence of a children by checking if its index is still in range with the list.

def _is_min_heap(L, i):
    l, r = 2 * i + 1, 2 * i + 2

    if r < len(L): # has left and right children
        if L[l] < L[i] or L[r] < L[i]: # heap property is violated
            return False

        # check both children trees
        return _is_min_heap(L, l) and _is_min_heap(L, r)
    elif l < len(L): # only has left children
        if L[l] < L[i]: # heap property is violated
            return False

        # check left children tree
        return _is_min_heap(L, l)
    else: # has no children
        return True

这篇关于是最小堆功能的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！