diff --git a/libcxx/docs/Status/Cxx2bIssues.csv b/libcxx/docs/Status/Cxx2bIssues.csv
--- a/libcxx/docs/Status/Cxx2bIssues.csv
+++ b/libcxx/docs/Status/Cxx2bIssues.csv
@@ -67,7 +67,7 @@
 `3430 <https://wg21.link/LWG3430>`__,"``std::fstream`` & co. should be constructible from string_view","June 2021","",""
 `3462 <https://wg21.link/LWG3462>`__,"§[formatter.requirements]: Formatter requirements forbid use of ``fc.arg()``","June 2021","",""
 `3481 <https://wg21.link/LWG3481>`__,"``viewable_range`` mishandles lvalue move-only views","June 2021","",""
-`3506 <https://wg21.link/LWG3506>`__,"Missing allocator-extended constructors for ``priority_queue``","June 2021","",""
+`3506 <https://wg21.link/LWG3506>`__,"Missing allocator-extended constructors for ``priority_queue``","June 2021","|Complete|","13.0"
 `3517 <https://wg21.link/LWG3517>`__,"``join_view::iterator``'s ``iter_swap`` is underconstrained","June 2021","",""
 `3518 <https://wg21.link/LWG3518>`__,"Exception requirements on char trait operations unclear","June 2021","",""
 `3519 <https://wg21.link/LWG3519>`__,"Incomplete synopses for <random> classes","June 2021","",""
diff --git a/libcxx/include/queue b/libcxx/include/queue
--- a/libcxx/include/queue
+++ b/libcxx/include/queue
@@ -115,27 +115,39 @@
     priority_queue() : priority_queue(Compare()) {} // C++20
     explicit priority_queue(const Compare& x) : priority_queue(x, Container()) {}
     priority_queue(const Compare& x, const Container&);
-    explicit priority_queue(const Compare& x = Compare(), Container&&= Container()); // before C++20
+    explicit priority_queue(const Compare& x = Compare(), Container&& = Container()); // before C++20
     priority_queue(const Compare& x, Container&&); // C++20
     template <class InputIterator>
         priority_queue(InputIterator first, InputIterator last,
                        const Compare& comp = Compare());
     template <class InputIterator>
         priority_queue(InputIterator first, InputIterator last,
-                       const Compare& comp, const container_type& c);
+                       const Compare& comp, const Container& c);
     template <class InputIterator>
         priority_queue(InputIterator first, InputIterator last,
-                       const Compare& comp, container_type&& c);
+                       const Compare& comp, Container&& c);
     template <class Alloc>
         explicit priority_queue(const Alloc& a);
     template <class Alloc>
         priority_queue(const Compare& comp, const Alloc& a);
     template <class Alloc>
-        priority_queue(const Compare& comp, const container_type& c,
+        priority_queue(const Compare& comp, const Container& c,
                        const Alloc& a);
     template <class Alloc>
-        priority_queue(const Compare& comp, container_type&& c,
+        priority_queue(const Compare& comp, Container&& c,
                        const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Compare& comp, const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Compare& comp, const Container& c, const Alloc& a);
+    template <class InputIterator>
+        priority_queue(InputIterator first, InputIterator last,
+                       const Compare& comp, Container&& c, const Alloc& a);
     template <class Alloc>
         priority_queue(const priority_queue& q, const Alloc& a);
     template <class Alloc>
@@ -160,15 +172,30 @@
     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 
 template<class InputIterator,
-         class Compare = less<typename iterator_traits<InputIterator>::value_type>,
-         class Container = vector<typename iterator_traits<InputIterator>::value_type>>
+         class Compare = less<typename iter-value-type<InputIterator>>,
+         class Container = vector<typename iter-value-type<InputIterator>>>
 priority_queue(InputIterator, InputIterator, Compare = Compare(), Container = Container())
-    -> priority_queue<typename iterator_traits<InputIterator>::value_type, Container, Compare>; // C++17
+    -> priority_queue<typename iter-value-type<InputIterator>, Container, Compare>; // C++17
 
 template<class Compare, class Container, class Allocator>
 priority_queue(Compare, Container, Allocator)
     -> priority_queue<typename Container::value_type, Container, Compare>; // C++17
 
+template<class InputIterator, class Allocator>
+priority_queue(InputIterator, InputIterator, Allocator)
+    -> priority_queue<iter-value-type<InputIterator>,
+                      vector<iter-value-type<InputIterator>, Allocator>,
+                      less<iter-value-type<InputIterator>>>;
+
+template<class InputIterator, class Compare, class Allocator>
+priority_queue(InputIterator, InputIterator, Compare, Allocator)
+    -> priority_queue<iter-value-type<InputIterator>,
+                      vector<iter-value-type<InputIterator>, Allocator>, Compare>;
+
+template<class InputIterator, class Compare, class Container, class Allocator>
+priority_queue(InputIterator, InputIterator, Compare, Container, Allocator)
+    -> priority_queue<typename Container::value_type, Container, Compare>;
+
 template <class T, class Container, class Compare>
   void swap(priority_queue<T, Container, Compare>& x,
             priority_queue<T, Container, Compare>& y)
@@ -507,6 +534,31 @@
                        _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
 #endif // _LIBCPP_CXX03_LANG
 
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l,
+                       const value_compare& __comp, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l,
+                       const value_compare& __comp, const container_type& __c, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+
+#ifndef _LIBCPP_CXX03_LANG
+    template <class _InputIter, class _Alloc, class = _EnableIf<__is_cpp17_input_iterator<_InputIter>::value> >
+        _LIBCPP_INLINE_VISIBILITY
+        priority_queue(_InputIter __f, _InputIter __l,
+                       const value_compare& __comp, container_type&& __c, const _Alloc& __a,
+                       _EnableIf<uses_allocator<container_type, _Alloc>::value>* = 0);
+#endif  // _LIBCPP_CXX03_LANG
+
     _LIBCPP_NODISCARD_AFTER_CXX17 _LIBCPP_INLINE_VISIBILITY
     bool            empty() const {return c.empty();}
     _LIBCPP_INLINE_VISIBILITY
@@ -560,6 +612,33 @@
 >
 priority_queue(_Compare, _Container, _Alloc)
     -> priority_queue<typename _Container::value_type, _Container, _Compare>;
+
+template<class _InputIterator, class _Allocator,
+         class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>
+>
+priority_queue(_InputIterator, _InputIterator, _Allocator)
+    -> priority_queue<__iter_value_type<_InputIterator>,
+                      vector<__iter_value_type<_InputIterator>, _Allocator>,
+                      less<__iter_value_type<_InputIterator>>>;
+
+template<class _InputIterator, class _Compare, class _Allocator,
+         class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::value>,
+         class = _EnableIf<!__is_allocator<_Compare>::value>,
+         class = _EnableIf<__is_allocator<_Allocator>::value>
+>
+priority_queue(_InputIterator, _InputIterator, _Compare, _Allocator)
+    -> priority_queue<__iter_value_type<_InputIterator>,
+                      vector<__iter_value_type<_InputIterator>, _Allocator>, _Compare>;
+
+template<class _InputIterator, class _Compare, class _Container, class _Alloc,
+         class = _EnableIf<__is_cpp17_input_iterator<_InputIterator>::value>,
+         class = _EnableIf<!__is_allocator<_Compare>::value>,
+         class = _EnableIf<!__is_allocator<_Container>::value>,
+         class = _EnableIf<uses_allocator<_Container, _Alloc>::value>
+>
+priority_queue(_InputIterator, _InputIterator, _Compare, _Container, _Alloc)
+    -> priority_queue<typename _Container::value_type, _Container, _Compare>;
 #endif
 
 template <class _Tp, class _Container, class _Compare>
@@ -669,7 +748,6 @@
     : c(__q.c, __a),
       comp(__q.comp)
 {
-    _VSTD::make_heap(c.begin(), c.end(), comp);
 }
 
 #ifndef _LIBCPP_CXX03_LANG
@@ -695,11 +773,65 @@
                        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
     : c(_VSTD::move(__q.c), __a),
       comp(_VSTD::move(__q.comp))
+{
+}
+
+#endif  // _LIBCPP_CXX03_LANG
+
+template <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
+    : c(__f, __l, __a),
+      comp()
 {
     _VSTD::make_heap(c.begin(), c.end(), comp);
 }
 
-#endif // _LIBCPP_CXX03_LANG
+template <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l,
+        const value_compare& __comp, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
+    : c(__f, __l, __a),
+      comp(__comp)
+{
+    _VSTD::make_heap(c.begin(), c.end(), comp);
+}
+
+template <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l,
+        const value_compare& __comp, const container_type& __c, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
+    : c(__c, __a),
+      comp(__comp)
+{
+    c.insert(c.end(), __f, __l);
+    _VSTD::make_heap(c.begin(), c.end(), comp);
+}
+
+#ifndef _LIBCPP_CXX03_LANG
+template <class _Tp, class _Container, class _Compare>
+template <class _InputIter, class _Alloc, class>
+inline
+priority_queue<_Tp, _Container, _Compare>::priority_queue(
+        _InputIter __f, _InputIter __l, const value_compare& __comp,
+        container_type&& __c, const _Alloc& __a,
+        _EnableIf<uses_allocator<container_type, _Alloc>::value>*)
+    : c(_VSTD::move(__c), __a),
+      comp(__comp)
+{
+    c.insert(c.end(), __f, __l);
+    _VSTD::make_heap(c.begin(), c.end(), comp);
+}
+#endif  // _LIBCPP_CXX03_LANG
 
 template <class _Tp, class _Container, class _Compare>
 inline
diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_alloc.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_alloc.pass.cpp
@@ -0,0 +1,37 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+#include <cstddef>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    using std::priority_queue<T, Cont, Comp>::priority_queue;
+    using std::priority_queue<T, Cont, Comp>::c;
+};
+
+int main(int, char**)
+{
+    int a[] = {3, 5, 2, 0, 6, 8, 1};
+    typedef test_allocator<int> Alloc;
+    PQ<int, std::vector<int, Alloc> > q(a, a+7, Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == 8);
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}
diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_alloc.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_alloc.pass.cpp
@@ -0,0 +1,38 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last, const Compare& comp, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+#include <functional>
+#include <cstddef>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    using std::priority_queue<T, Cont, Comp>::priority_queue;
+    using std::priority_queue<T, Cont, Comp>::c;
+};
+
+int main(int, char**)
+{
+    int a[] = {3, 5, 2, 0, 6, 8, 1};
+    typedef test_allocator<int> Alloc;
+    PQ<int, std::vector<int, Alloc>, std::greater<int> > q(a, a+7, std::greater<int>(), Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == 0);
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}
diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_cont_alloc.pass.cpp
@@ -0,0 +1,38 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last,
+//                  const Compare& comp, const Container& c, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    using std::priority_queue<T, Cont, Comp>::priority_queue;
+    using std::priority_queue<T, Cont, Comp>::c;
+};
+
+int main(int, char**)
+{
+    typedef test_allocator<int> Alloc;
+    int a[] = {3, 5, 2, 0, 6, 8, 1};
+    std::vector<int, Alloc> v(a, a+3);
+    PQ<int, std::vector<int, Alloc> > q(a+3, a+7, std::less<int>(), v, Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == 8);
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}
diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_rcont_alloc.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_rcont_alloc.pass.cpp
new file mode 100644
--- /dev/null
+++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons.alloc/ctor_iter_iter_comp_rcont_alloc.pass.cpp
@@ -0,0 +1,42 @@
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03
+
+// <queue>
+
+// template <class InputIterator>
+//   priority_queue(InputIterator first, InputIterator last,
+//                  const Compare& comp, Container&& c, const Alloc& a);
+
+#include <queue>
+#include <cassert>
+
+#include "test_macros.h"
+#include "test_allocator.h"
+#include "MoveOnly.h"
+
+template<class T, class Cont, class Comp = std::less<T> >
+struct PQ : std::priority_queue<T, Cont, Comp> {
+    using std::priority_queue<T, Cont, Comp>::priority_queue;
+    using std::priority_queue<T, Cont, Comp>::c;
+};
+
+int main(int, char**)
+{
+    using Alloc = test_allocator<MoveOnly>;
+    int a[] = {3, 5, 2, 0, 6, 8, 1};
+    PQ<MoveOnly, std::vector<MoveOnly, Alloc>> q(
+        a+3, a+7, std::less<MoveOnly>(),
+        std::vector<MoveOnly, Alloc>(a, a+3), Alloc(2));
+    assert(q.size() == 7);
+    assert(q.top() == MoveOnly(8));
+    assert(q.c.get_allocator() == Alloc(2));
+
+    return 0;
+}
diff --git a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp
--- a/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp
+++ b/libcxx/test/std/containers/container.adaptors/priority.queue/priqueue.cons/deduct.pass.cpp
@@ -173,6 +173,70 @@
         std::priority_queue pri(std::move(source), ConvertibleToAlloc(2));
         static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
         }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), cont, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), cont, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), std::move(cont), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        std::priority_queue pri(Comp(), std::move(cont), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>>>);
+        }
+
+        {
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, std::vector<T, Alloc>, Comp>>);
+        }
+
+        {
+        Cont cont;
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), cont, Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), cont, ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), std::move(cont), Alloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
+
+        {
+        Cont cont;
+        T a[2] = {};
+        std::priority_queue pri(a, a+2, Comp(), std::move(cont), ConvertibleToAlloc(2));
+        static_assert(std::is_same_v<decltype(pri), std::priority_queue<T, Cont, Comp>>);
+        }
     }
 
     return 0;