Different MultiSet and Heap

This is a discussion on Different MultiSet and Heap within the C++ Programming forums, part of the General Programming Boards category; I don't know what different in C++ between this data structure. I know that MultiSet is a set that has ...

  1. #1
    hqt
    hqt is offline
    Registered User
    Join Date
    Aug 2011
    Posts
    115

    Question Different MultiSet and Heap

    I don't know what different in C++ between this data structure. I know that MultiSet is a set that has many same keys, and Heap is like binary Search Tree. MultiSet/Set, I have read that C++ use interval tree for this data structure. So, what is real different between MultiSet and Heap in C++.
    thanks

  2. #2
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    The only "heap" I know of in C++ is the algorithms: make_heap, push_heap, pop_heap, sort_heap. These are meant to be used on a vector, and enforce the properties of a heap data structure. If you don't know what a heap data structure is, you should look that up. Also, the priority_queue uses a heap structure.

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,310
    Refer to your DADS:

    bag (multiset): An unordered collection of values that may have duplicates.

    heap: A complete tree where every node has a key more extreme (greater or less) than or equal to the key of its parent. Usually understood to be a binary heap.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    A heap is not like a binary search tree. Yes internally it has a notion of parent/child relationships and a multiset may be implemented that way, but that's about where the similarity ends. Externally a Binary Search Tree has O(log n) search time whereas a heap doesn't support searching so it would take O(n). A heap can tell you the minimum item immediately. A binary search tree may have to visit a lot of nodes to do so. A BST allows you to visit all items in sorted order but a heap cannot do that at all. A heap requires copying items and moving them around to perform insertion or removals, but a BST doesn't. A heap is very very different from a BST.

    What you're actually doing is comparing a container with a data structure.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Multiset stl
    By dpp in forum C++ Programming
    Replies: 3
    Last Post: 03-29-2009, 08:42 AM
  2. making multiset destructor faster...
    By bling in forum C++ Programming
    Replies: 2
    Last Post: 08-30-2008, 11:56 AM
  3. multiset and classes
    By quizkiwi in forum C++ Programming
    Replies: 10
    Last Post: 08-30-2004, 06:08 PM
  4. Anyone Know HEAP ?
    By Kam in forum C Programming
    Replies: 5
    Last Post: 09-14-2002, 07:47 AM
  5. heap
    By Unregistered in forum C++ Programming
    Replies: 1
    Last Post: 12-10-2001, 01:15 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21