Advertisement
Guest User

Untitled

a guest
Jul 21st, 2017
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.79 KB | None | 0 0
  1. [90, 15, 10, 7, 12, 2]
  2.  
  3. 15, 10,
  4. [(90), 7, 12, 2]
  5.  
  6. 7, 12,
  7. [90, (15), 10, 2]
  8.  
  9. 2
  10. [90, 15, (10), 7, 12, ]
  11.  
  12. [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
  13.  
  14. //0-indexing:
  15. child1 = (i * 2) + 1
  16. child2 = (i * 2) + 2
  17.  
  18. //1-indexing:
  19. child1 = (i * 2)
  20. child2 = (i * 2) + 1
  21.  
  22. def is_heap(l):
  23. for head in range(0, len(l)):
  24. c1, c2 = head * 2 + 1, head * 2 + 2
  25. if c1 < len(l) and l[head] < l[c1]:
  26. return False
  27. if c2 < len(l) and l[head] < l[c2]:
  28. return False
  29.  
  30. return True
  31.  
  32. [90, 15, 10, 7, 12, 2]
  33. [93, 15, 87, 7, 15, 5]
  34. [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
  35. [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
  36. [100, 19, 36, 17, 3, 25, 1, 2, 7]
  37. [5, 5, 5, 5, 5, 5, 5, 5]
  38.  
  39. [4, 5, 5, 5, 5, 5, 5, 5]
  40. [90, 15, 10, 7, 12, 11]
  41. [1, 2, 3, 4, 5]
  42. [4, 8, 15, 16, 23, 42]
  43. [2, 1, 3]
  44.  
  45. x2:ḊṂ
  46.  
  47. x2 Duplicate each element.
  48. :Ḋ Each element divided by the input with the first element removed,
  49. as integer, so there is a 0 only if some element in the duplicated
  50. list is less than the corresponding element in the other.
  51. There are also elements left unchanged, but it doesn't matter as
  52. the input is all positive.
  53. Ṃ Minimum in the list.
  54.  
  55. a=>!a.some((e,i)=>e>a[i-1>>1])
  56.  
  57. */@:<:]{~0}:@,<.@-:@i.@#
  58.  
  59. */@:<:]{~0}:@,<.@-:@i.@# Input: s
  60. # Count of s
  61. i.@ Create range [0, 1, ..., len(s)-1]
  62. -:@ Halve each
  63. <.@ Floor each
  64. 0 , Prepend a zero to it
  65. }:@ Remove the last value to get the parent indices of each
  66. ] Identity function to get s
  67. {~ Take the values from s at the parent indices
  68. <: For each, 1 if it is less than or equal to its parent else 0
  69. */@: Reduce using multiplication and return
  70.  
  71. ttf2/k)>~4L)
  72.  
  73. t % Take input implicitly. Duplicate
  74. tf % Duplicate and push indices of nonzero entries. This gives [1 2 ... n] where n
  75. % is input size
  76. 2/k % Divide by 2 and round down
  77. ) % Index into input. Gives array of parents, except for the first entry
  78. >~ % True for entries of the input that don't exceed those in the array of parents
  79. 4L) % Discard first entry
  80.  
  81. function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)
  82.  
  83. > f=
  84. + function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)
  85. > f(c(90, 15, 10, 7, 12, 2))
  86. [1] TRUE
  87. > f(c(93, 15, 87, 7, 15, 5))
  88. [1] TRUE
  89. > f(c(10, 9, 8, 7, 6, 5, 4, 3, 2, 1))
  90. [1] TRUE
  91. > f(c(5, 5, 5, 5, 5, 5, 5, 5))
  92. [1] TRUE
  93. > f(c(4, 5, 5, 5, 5, 5, 5, 5))
  94. [1] FALSE
  95. > f(c(90, 15, 10, 7, 12, 11))
  96. [1] FALSE
  97. > f(c(4, 8, 15, 16, 23, 42))
  98. [1] FALSE
  99.  
  100. q~_:_(;./:*
  101.  
  102. .AgV.i+h
  103.  
  104. hQ first element of input
  105. + Q plus input
  106. .i Q interleaved with input
  107. gV Q vectorized greater-than-or-equal comparison with input
  108. .A check if all results are true
  109.  
  110. x=scan();all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)
  111.  
  112. x=scan();
  113.  
  114. x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)]
  115.  
  116. diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)
  117.  
  118. all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)
  119.  
  120. ;;2╟┬Σ1(tZ`i<`Mm
  121.  
  122. Implicit input a.
  123. ;; Duplicate a twice.
  124. 2╟ Wrap two of the duplicates into a list.
  125. ┬ Transpose the duplicates.
  126. Σ Sum all of the columns to get a flat list like this:
  127. [a_0, a_0, a_1, a_1, ..., a_n, a_n]
  128. This gets the parent nodes of the heap.
  129. 1(t Get a[1:] using the remaining duplicate of a.
  130. This is a list of the child nodes of the heap.
  131. Z`i<`M Check if every child node is less than its parent node.
  132. m Get the minimum. This returns 1 if a is a max-heap, else 0.
  133. Implicit return.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement