If we construct sorted set based on RB Tree and Heap. Do insertion() and deleteMax() for n times.

(1). What's the Big-O ?

My idea: For both RB tree and heap , deleteMax() and insertion() will all take nlog(n), so does it mean the time complexity will be O(nlog(n) + nlog(n)) = O(2nlog(n)) ?

(2). How about the difference of their constant factors.

Assume you are talking about binary heap. For each insertion/maxDeletion, the time complexity is `O(log(n))`

for both RB and binary heap, where `n`

is the number of existing elements in the RB/heap. Fibonacci heap has better theoretical time complexity. You should read the wiki.

As to the constant, binary heap is better than RB. It is also much easier to implement and takes less space. You should use heap when you only want to keep track of the min/max without requiring to know the complete ordering of all elements.

Similar Questions

In a tree I have to find two vertices which have maximum number of vertices between them (connected) including both of them. Then I need to find the total number of vertices between them. I want to ap

Hi I have been searching for some good information about how I can make a sorted binary tree datatype in F# but i cant find anything understandable. I have checked the example on msdn-page but i dont

So if I have to choose between a hash table or a prefix tree what are the discriminating factors that would lead me to choose one over the other. From my own naive point of view it seems as though usi

What is the difference between SIGTERM and SIGKILL when it comes to the process tree? When a root thread recieves SIGKILL does it get killed cleanly or does it leave it's child threads as zombies? Is

I'm using Jackson 2.2.3 and need to convert a JsonNode tree into a string with sorted field keys. It's completely unclear to me how to do this, especially since the opposite is so simple - JsonNode jn

I am reading Binomial Heap in Purely Functional Data Structures. The implementation of insTree function confused me quite much. Here are the set of codes datatype Tree = Node of int * Elem.T * Tree l

What is the difference between binary search and binary search tree? Are they the same? reading the internet it seams the second is only for trees(up to 2 children nodes) and binary search doesn't fol

Following my previous question, I would like now to put the Binary Tree values in a sorted array. So, first I used my numOfNodeswn function that counts total sum of nodes in my tree, I created an arr

I would like to know if there exist algorithms that solves this issue. It is little bit similar to knapsack 0-1 problem, or power set problem however it is different. Given a finite set of sorted rea

Let A be a list and S a sorted list of the same elements. Assume all elements are different. How do I find a minimal set of moves (move X before Y (or end)) that turns A into S? Examples: A = [8,1,2

In my spec folder, I have both a rails_helper.rb file and a spec_helper.rb file. If I have nothing being required for rails_helper.rb, is it safe to delete? Is there any difference or pros and cons to

I know there's Dalvik(JVM) heap and Native heap in an android platform. And the Dalvik GC has no work on native heap. But I'm not sure how this work, I mean how the Android OS separate them? possible

Is there any difference between statements ALTER TABLE xxx DEFAULT CHARACTER SET utf8 and ALTER TABLE xxx CHARACTER SET utf8 ? MySQL documentation keeps silence about functionality of DEFAULT keyword.

Say I have a sorted-set of integers, xs, and I want to retrieve all the integers in xs that are [x, y), ie. between x and y. I can do: (select #(and (>= % x) (< % y)) xs) But this is inefficien

First i insert the Heap into an Array (according to Level order (aka Breadth first) traversal), and now i check the array For i = 1 to Len(Array) do: IF 2 * i smaller than Len(Array): IF Array[i] sma

In qooxdoo's tree you can setMaxHeight for each tree item: var tree = new qx.ui.tree.Tree(); tree.set({ width: 500, height: 500 }); this.getRoot().add(tree, {left: 10, top: 10}); // create and set the

How can one create a Set object that stores its elements on the heap in a dynamic array of int values? In particular, how does one create an empty set with these specifications? // Morally Right (M) 2

I am trying to store media objects and have them retrievable by a certain time range through redis. I have chosen a sorted set data type to do this. I am adding elements like: zAdd: key: media:552672

I'm looking for a data structure where each element in it has two keys. With one of them the structure is a BST and looking at the other one, data structure is a heap. With a little search, I found a

When I compile in release mode, I have heap corruption on the deallocation of a std::string. In fact, in a DLL named Atc.dll, I call a function which is in another DLL named Utilies.dll. At the end o

I need an algorithm for computation convex hulls for sorted set of points in 3 and higher dimensions. Also I need in lower part of a convex hull and it is not necessary to construct a whole convex hul

If I am attempting to minimize the height of a Binary Search Tree, are these the correct steps?: 1) produce a sorted array from the tree 2) reconstruct the tree by adding the sorted elements into the

Can anyone tell the differences between set and setRepeat methods of AlarmManager class ?

I have this code for a heap tree and I'm stuck with the iterators. I need in-order, pre-order and post-order iterators, but I have no idea how to do it. If someone has an idea or example please help.

When making a binary max heap, why is it better to implement it as a array based, and not a tree based (tree based as in, each node also having a pointer to it's parent)? In terms of run time analysis

I'm trying to write a result set (100,000 rows, 45 cols) from a web application to excel using JExcel 2.6.9. The process fails with: Caused by: java.lang.OutOfMemoryError - Java heap space at jxl.writ

I know about this question, but it's about B-tree and B+-tree. Sorry, if there's similar for B*-tree, but I couldn't find such. So, what is the difference between these two trees? The wikipedia articl

Tree traversal refers to the process of visiting each node in a tree data structure in a systematic way. The postorder traversal in the following image Sorted_binary_tree returns A, C, E, D, B, H, I,

I am running a server with the following attributes: Windows Server 2008 R2 Standard - 64bit 4gb RAM I am trying to set the heap size to 3gb for an application. I am using the flags -Xmx3G -Xms3G. Run

I'm trying to translate the following piece of code into Ruby using the rb-appscript gem: tell application System Events to tell process Dock set dock_dimensions to size in list 1 set dock_height

It seems that a priority queue is just a heap with normal queue operations like insert, delete, top, etc. Is this the correct way to interpret a priority queue? I know you can build priority queues in

I am using Jconsole for monitoring a Java Application. The memory tab shows different Heap and Non Heap memories like Heap Memory Usage Non Heap Memory Usage Memory Pool CMS Old Gen Memory Pool Pa

How do I copy a sorted set in redis to a regular, unsorted set? Is there a redis command that can do this? I can manually iterate through the sorted set and manually insert in the unsorted set, but it

Hi I have studied min heap and max heap and I have these questions that - a sorted array is a min heap? - where is the minimum value of a max heap? please help me thanks {if you put some link I will

We are given an array of 2m - 1 distinct, comparable elements, indexed starting from 1. We can view the array as a complete binary tree: Node is placed at index i. Left child is placed at 2i. Right ch

I'm hitting some kind of mental roadblock related to destructuring... (sorted-set 4 2 5) gives: #{2 4 5} But How I can get that same sorted set from: ((fn [???] (sorted-set ???)) [4 2 5]) or from a

Let's say I have this data structure for a minimum heap: struct node{ int height; struct node *parent; struct node *left; struct node *right; }; What I want to do is add a new node into the next avai

I would like to know if there is an algorithm which computes a minimum spanning tree (optimum branching) in a directed graph given a set of root vertices between all of these root vertices, but not on

void heapSort(int list[], int last) { // Local Declarations int sorted; int holdData; int walker; // Statements for (walker = 1; walker <= last; walker++) reheapUp (list, walker); // Min Heap creat

Unable to set java heap space using -Xmx to 2GB or more even though the RAM size is 16GB. I encounter an error saying Error: Could not create the Java Virtual Machine. Error: A fatal exception has o

For a lazy loaded tree using JsonRestStore and ForestModel, where would I set an additional query parameter to be included in expand requests? I have declared the additional parameters in the SMD, but

Is it possible to take a heap handle from HeapCreate() and set all available memory to a certain value? I've tried enumerating the heap by region and setting it that way, but I get access violations.

We know that heaps and red-black tree both have these properties: worst-case cost for searching is lgN; worst-case cost for insertion is lgN. So, since the implementation and operation of red-black

Possible Duplicate: What and where are the stack and heap Where is heap memory and stack memory stored?I mean where on the harddisk?what are the limits of their size?

I know we can preprocess and turn any binary search tree into a perfect binary tree using DSW algorithm or red black balanced trees. How do these two methods differ time-complexity wise? Can you provi

I have a sorted set which has the following key name and values : zrange bargraph:branch:1:category:2:product:4 1) 76 2) 55 3) 10 4) 84 Is there a mechanism in redis where I can use a wildca

I use Redis as persistence of my data in sorted set. My data looks like the following: {text: 'Some text1', data: [1, 2, 3]}, {test: 'Some text2', data: [1, 3]} . . . How to update some element in th

I'm working with C++ in Visual Studio 2010. I have an STL set, which I'm saving to file when my program shuts down. The next time the program starts up, I load the (sorted) data back into a set. I'm t

I've downloaded the movies from IMDB (movies-list) from here: http://www.imdb.com/interfaces I want to count how often a given movie appears in the list with help of Redis sorted sets, but I am bit co

I have a Sorted set and want to get all members of set. How to identify a max/min score for command : zrange key min max ?