# Tagged Questions

The tag has no usage guidance.

37 views

### Priority Queue: Specific Construction Question

The problem: Let n be any positive integer. Is it possible to construct a priority queue A of size n with the property that at every iteration of operation DELETEMIN the process substituting the ...
46 views

### Efficient haircuts

I have a real vector $v$. From this vector, I want to extract a sequence of integers, $ix$. The first integer is found by, $ix_0=argmax(v)$. 1 is then subtracted from $v_{ix_0}$, and the process is ...
407 views

### Finding the median in a heap

Given a binary heap $H$, indexed in $[1..n]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?
91 views

### Why in a min priority queue (heap based) it is called “decrease-key” and not just “set-key”?

When you call decrease-key in a min priority queue, you are basically setting the key, you can accidentally put a higher key, right? so why isn't it called "set-key" or "update-key"? why (according to ...
169 views

### Heap-like data structure allowing peek at largest & smallest

For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations: load from array ...
2k views

### How to calculate probability of packet loss and drop rate?

In a queuing system (M/M/1) with a finite packet capacity $z$, how do you determine the probability of packet loss if we assume that packets are dropped when the system is full? Packets arrive with a ...
572 views

### Where To Put Duplicates in Max Heap?

Question: Suppose you have a list of integers and it might contain duplicates. Build a Max Heap using this list. Where would the duplicates of the max integer reside in this Max Heap data ...
65 views

### What will trigger a worst time search for a binary heap and what is the run time? [closed]

I thought if the values in a max or min heap is monotonically increasing or decreasing, then this will trigger a worst case run time of $\mathcal{O}(n)$ because you will have to go through each and ...
203 views

### Dynamically weighted priority queue?

Elements are stored in a single dynamic data-structure $D$ Element ranks are computed by: $\forall i \in n\quad f(i,\ x_i+1) : x_i \in \mathbb{Z^+}$ The function $f$ is weighting based on the value of ...