Is destructuring a heap (taking down a heap) also O(n) like building a heap? If so, can the selection problem be solved by this method in O(n) time?

If we can build up a heap with time O(n), can we take down a heap also by O(n)? (by delete-max repeatedly).

Intuitively, it may feel it is, because it is like the reverse of build it up.

If building a heap is O(n) in the worst case, including the numbers are all adding by ascending order, then taking the heap down is exactly the “reverse in time” operation, and it is O(n), but this may not be the “worst case” of taking it down.

If taking down a heap is really O(n), can’t the selection problem be solved by building a heap, and then taking it down (k – 1) time, to find the kth max number?

finding the parent index in an interval heap (stored on an array) given a child index

an interval heap is a binary tree stored on an array where the size of each node is 2.

i would like to be able to find the index of a parent and find one of the child indices given the index of a node.

an example of an interval trees indices would be:

         [0,1]      [2,3]     [4,5]  [6,7][8,9][10,11][12,13] 

or

         [1,2]      [3,4]     [5,6]  [7,8][9,10][11,12][13,14] 

Relation Between Priority Queue, Heap, Tree

There are $ 2$ “basic”/”fundamental” data structures due to the way memory works:

  1. array
  2. linked list

Then there are ADT that we implement using those two, for example: stack, queue and more.

When we arrive to priority queue we first need to implement and ADT called heap which can be implement using:

  1. array
  2. tree (which is ADT) the can be implemented using both array and linked list

So we have

array/linked list $ \subset$ tree $ \subset$ priority queue?

enter image description here

Minimum number of elements in a heap of height $h$

I came across this Question in Introduction To Algorithms:

What are the maximum and minimum number of elements in a heap of height $ h$ ?

I could figure out the maximum number of elements in a heap of height $ h$ is: $ 2^{h+1}-1$ .

But I am having a hard time understanding that the minimum number of elements in a heap of height $ h$ is $ 2^{h}$ .

What I have tried is:

Because we can consider that level $ h-1$ is completely filled.

So the total elements at $ h-1$ are: $ 2^{h}-1$

The solutions on the Internet stated this fact:

Clearly a heap of height $ h$ has the minimum number of elements when it has just one node at the lowest level.

So using this it is easy to compute elements, i.e:

$ 2^{h}-1+1=2^{h}$ elements.

But I had read the property of Complete Binary Tree that the node can have $ 0$ or $ 2$ children.

So using this won’t we add 2 instead of adding one. i.e: $ 2^{h}-1+1$

Should be replaced with: $ 2^{h}-1+2$ . Thus, the number of nodes should be $ 2^{h}+1$ instead of $ 2^{h}$ .

Please Help. Thank you.

Proving $h=\lceil \log_2(n+1) \rceil-1 = \lfloor \log_2n \rfloor$ to prove that n-element heap has height $\lfloor \log_2n\rfloor$

I am stuck on proving the height of $ n$ -element heap is equal to $ \lfloor log_2 n\rfloor$

I managed to understand everything else but cannot understand how to deduce this step from the inequality:

$ \log_2(n+1)-1 \le h \le \log_2n$

I cannot understand the following step:

$ h=\lceil \log_2(n+1) \rceil-1 = \lfloor \log_2n \rfloor$

I looked at the answer here: https://www.quora.com/Why-must-a-heap-of-size-n-have-height-floor-log-n

Please help. Thank you.

Max heap and array relation

This question is about max heap and array

Suppose there is max heap h , if n data already stored in heap h. An array that is formed by inserting a value larger than all the value in heap at the beginning/head of the heap h is assumed to be new array C . The array C is a heap (or) not ?

My answer: is heap because its bigger than any other element in array

if n data already stored in heap h. A new array D that is created by adding a value u to the heap h that is smaller than any of the n data already stored in heap . if u is added to last element in heap h, is Array D heap or not?

My answer: it is heap because the smallest one has to be in the leaf

But what is the relation with array? Is there rule to insert node in heap? I know that to insert node to array in heap we insert data as last element of heap and then put it in the root and heapify it

A single heap nim game

Consider a game where two players remove sticks from a heap. The players move alternately, and the player who removes the last stick wins the game.

A set P = {p1,p2,โ€ฆ,pk} determines the allowed moves. For example, if P = {1,3,4}, a player may remove 1, 3 or 4 sticks.

Your task is find out for each number of sticks 1 , 2 ,โ€ฆ, n if the first player has a winning or losing position.

How to solve this question. Thank You for help.

Heap down – What is math logic and intuition behind $\sum_{i=1}^{log(n)}(logn – i).2^i $

In heap (bubble down) we have the formula : $ \sum_{i=1}^{log(n)}(logn – i).2^i = logn\sum_{i=1}^{log(n)}2^i -logn\sum_{i=1}^{log(n)}i.2^i = log๐‘›.2^{log๐‘›+1}-(log๐‘›.2^{log๐‘›+1}-(2^{log๐‘›+1}โˆ’2))=2๐‘›โˆ’2โˆˆฮ˜(๐‘›) $

  1. Why we have $ \sum_{i=1}^{log(n)}(logn – i).2^i$ ?
  2. How we get to $ 2๐‘›โˆ’2โˆˆฮ˜(๐‘›)$ ?

Please explain details!