它是最大的堆吗？

Question

堆堆 (也称为优先级队列)是一种抽象数据类型.从概念上讲，它是一个二叉树，每个节点的子节点都小于或等于节点本身。(假设它是一个最大的堆。)当一个元素被推送或弹出时，堆会重新排列自己，因此最大的元素是下一个要弹出的元素。它可以很容易地作为树或数组来实现。

如果您选择接受它，您的挑战是确定数组是否是有效的堆。如果每个元素的子元素小于或等于元素本身，则数组以堆形式出现。以以下数组为例：

[90, 15, 10, 7, 12, 2]

实际上，这是一棵以数组形式排列的二叉树。这是因为每个元素都有子元素。90岁有两个孩子，15岁和10岁。

       15, 10,
[(90),         7, 12, 2]

15名儿童，7岁和12岁：

               7, 12,
[90, (15), 10,        2]

10名有子女：

                      2
[90, 15, (10), 7, 12,  ]

下一个元素也是一个10岁的孩子，只是没有空间。如果数组足够长，7、12和2都会有子。下面是堆的另一个示例：

[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]

下面是前面的数组所做的树的可视化：

如果这还不够清楚，下面是得到I‘’th元素的子元素的显式公式。

//0-indexing:
child1 = (i * 2) + 1
child2 = (i * 2) + 2

//1-indexing:
child1 = (i * 2)
child2 = (i * 2) + 1

如果数组是按堆顺序排列的，则必须将非空数组作为输入并输出一个真实值，否则输出一个假值。这可以是0索引堆，也可以是1索引堆，只要您指定程序/函数所期望的格式。您可以假设所有数组都只包含正整数。您可以不使用任何堆内置。这包括但不限于

• 函数，该函数确定数组是否为堆形式。
• 将数组转换为堆或堆形式的函数。
• 函数，这些函数以数组作为输入并返回堆数据结构。

您可以使用这个python脚本来验证数组是否为堆形式(0索引)：

def is_heap(l):
    for head in range(0, len(l)):
        c1, c2 = head * 2 + 1, head * 2 + 2
        if c1 < len(l) and l[head] < l[c1]:
            return False
        if c2 < len(l) and l[head] < l[c2]:
            return False

    return True

测试IO:

所有这些输入都应该返回True：

[90, 15, 10, 7, 12, 2]
[93, 15, 87, 7, 15, 5]
[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
[100, 19, 36, 17, 3, 25, 1, 2, 7]
[5, 5, 5, 5, 5, 5, 5, 5]

所有这些输入都应该返回False：

[4, 5, 5, 5, 5, 5, 5, 5]
[90, 15, 10, 7, 12, 11]
[1, 2, 3, 4, 5]
[4, 8, 15, 16, 23, 42]
[2, 1, 3]

与往常一样，这是代码-高尔夫，所以标准漏洞应用和最短的答案字节赢！

Answer 1

J，24字节

*/@:<:]{~0}:@,<.@-:@i.@#

解释

*/@:<:]{~0}:@,<.@-:@i.@#  Input: s
                       #  Count of s
                    i.@   Create range [0, 1, ..., len(s)-1]
                 -:@      Halve each
              <.@         Floor each
         0   ,            Prepend a zero to it
          }:@             Remove the last value to get the parent indices of each
      ]                   Identity function to get s
       {~                 Take the values from s at the parent indices
    <:                    For each, 1 if it is less than or equal to its parent else 0
*/@:                      Reduce using multiplication and return

Answer 2

Python 2，45字节

f=lambda l:l==[]or l[len(l)/2-1]/l.pop()*f(l)

为Falsy输出0，为Truthy输出非零。

检查最后一个元素在索引len(l)/2-1处是否小于或等于其父元素。然后，递归检查列表中的最后一个元素是否为True，以此类推，直到列表为空。

48字节：

f=lambda l,i=1:l==l[:i]or l[~-i/2]/l[i]*f(l,i+1)

检查在每个索引i上，元素至多是索引(i-1)/2的父元素。如果不是这样的话，地板分割会产生0。

以i/len(l)or的形式执行基本情况会给出相同的长度。我一开始试过压缩，但是代码更长(57个字节)。

lambda l:all(map(lambda a,b,c:b<=a>=c,l,l[1::2],l[2::2]))

Answer 3

维沙尔 r，5字节

hJY≥A

在网上试试！