Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- [90, 15, 10, 7, 12, 2]
- 15, 10,
- [(90), 7, 12, 2]
- 7, 12,
- [90, (15), 10, 2]
- 2
- [90, 15, (10), 7, 12, ]
- [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
- //0-indexing:
- child1 = (i * 2) + 1
- child2 = (i * 2) + 2
- //1-indexing:
- child1 = (i * 2)
- child2 = (i * 2) + 1
- 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
- [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]
- [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]
- x2:ḊṂ
- x2 Duplicate each element.
- :Ḋ Each element divided by the input with the first element removed,
- as integer, so there is a 0 only if some element in the duplicated
- list is less than the corresponding element in the other.
- There are also elements left unchanged, but it doesn't matter as
- the input is all positive.
- Ṃ Minimum in the list.
- a=>!a.some((e,i)=>e>a[i-1>>1])
- */@:<:]{~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
- ttf2/k)>~4L)
- t % Take input implicitly. Duplicate
- tf % Duplicate and push indices of nonzero entries. This gives [1 2 ... n] where n
- % is input size
- 2/k % Divide by 2 and round down
- ) % Index into input. Gives array of parents, except for the first entry
- >~ % True for entries of the input that don't exceed those in the array of parents
- 4L) % Discard first entry
- function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)
- > f=
- + function(Y)all(sapply(1:length(Y),function(X)Y[X]>=Y[X*2]&Y[X]>=Y[X*2+1]),na.rm=T)
- > f(c(90, 15, 10, 7, 12, 2))
- [1] TRUE
- > f(c(93, 15, 87, 7, 15, 5))
- [1] TRUE
- > f(c(10, 9, 8, 7, 6, 5, 4, 3, 2, 1))
- [1] TRUE
- > f(c(5, 5, 5, 5, 5, 5, 5, 5))
- [1] TRUE
- > f(c(4, 5, 5, 5, 5, 5, 5, 5))
- [1] FALSE
- > f(c(90, 15, 10, 7, 12, 11))
- [1] FALSE
- > f(c(4, 8, 15, 16, 23, 42))
- [1] FALSE
- q~_:_(;./:*
- .AgV.i+h
- hQ first element of input
- + Q plus input
- .i Q interleaved with input
- gV Q vectorized greater-than-or-equal comparison with input
- .A check if all results are true
- 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)
- x=scan();
- x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)]
- diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)
- all(diff(x[c(a<-1:(N<-sum(1|x)),a,a*2,a*2+1)],l=N*2)<1,na.rm=T)
- ;;2╟┬Σ1(tZ`i<`Mm
- Implicit input a.
- ;; Duplicate a twice.
- 2╟ Wrap two of the duplicates into a list.
- ┬ Transpose the duplicates.
- Σ Sum all of the columns to get a flat list like this:
- [a_0, a_0, a_1, a_1, ..., a_n, a_n]
- This gets the parent nodes of the heap.
- 1(t Get a[1:] using the remaining duplicate of a.
- This is a list of the child nodes of the heap.
- Z`i<`M Check if every child node is less than its parent node.
- m Get the minimum. This returns 1 if a is a max-heap, else 0.
- Implicit return.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement